[C/C++] 코드업(codeup) 4023번 오목

▽문제 바로가기

https://codeup.kr/problem.php?id=4023

오목

---

입력

입력 파일은 19줄에 각 줄마다 19개의 숫자로 표현되는데, 검은 바둑알은 1, 흰 바둑알은 2, 알이 놓이지 않은 자리는 0으로 표시되며, 숫자는 한 칸씩 띄어서 표시된다. 

 

출력

첫 번째 줄에 검은색이 이겼을 경우에는 1을, 흰색이 이겼을 경우에는 2를, 아직 승부가 결정되지 않았을 경우에는 0을 출력한다.

검은색 또는 흰색이 이겼을 경우에는 둘째 줄에 연속된 다섯 개의 바둑알 중에서 가장 왼쪽에 있는 바둑알(연속된 다섯 개의 바둑알이 세로로 놓인 경우, 그중 가장 위에 있는 것)의 가로줄 번호와 세로줄 번호를 순서대로 출력한다.

 

문제 풀이

 

출력해야 할 것은 무슨 색돌이 이겼는지와 오목의 가장 왼쪽의 시작 좌표를 출력해야 합니다. 따라서 모든 방향(8방향)으로 탐색하는 것은 그다지 좋아 보이지 않았습니다.

 

탐색을 할 방향은 총 4가지입니다.

 

1. 오른쪽가로

2. 밑으로세로

3. 오른쪽 대각선 아래

4. 오른쪽 대각선 위

 

이렇게 하면 시작점이 가장 왼쪽의 시작 좌표가 됩니다.

 

<가로, 세로, 몇 개 가연 속인지, 무슨 색돌인지, 4방향 중 어느 방향으로 나아가는지>

위의 정보를 매개변수로 받아서 탐색하였습니다.

다만 탐색 방향에 대해서 주의해야 합니다.

예를 들어 오른쪽 대각선 아래로 탐색하고 있을 때

 

1 0 0 0 0 0

0 1 0 0 0 0

0 0 1 0 0 0

0 0 0 1 0 0

0 0 0 0 1 0

0 0 0 0 0 1

 

위와 같은 경우 시작점을 (0, 0)이라고 했을 때 6목으로 판별됩니다.

하지만, (1, 1)에서 다시 탐색을 진행했을 때 5목으로 판별됩니다. 따라서 시작점에 대한 반대방향 값도 따져줘야 합니다.

예를 들어 (1, 1) 에서 대각선((2, 2) 방향)으로 탐색했을 경우 반대방향((0, 0) 방향)도 따져줘야 합니다.

 

#include <stdio.h>

using namespace std;

int arr[19][19] = {0,};
//가로, 세로, 대각선 아래, 대각선 위순
int dy[4] = {0, 1, 1, -1};
int dx[4] = {1, 0, 1, 1};
bool flag = false;	//승부가 났는지 판별 
int win, frow, fcol;	//이긴돌, 가로줄, 세로줄

//가로, 세로, 연속갯수, 무슨색돌인지, 어느방향인지
void dfs(int row, int col, int cnt, int who, int d){
	//범위밖이면 리턴 
	if(row==-1||col==-1||row==19||col==19) return;
	
	//5카운트에 다음방향값이 다른색이고, 반대방향도 다른색이면 5목, 승부남
	if((cnt==5)&&(arr[row+dy[d]][col+dx[d]]!=who)&&(arr[row-dy[d]*5][col-dx[d]*5]!=who)){
		flag = true;
		win = who;
		frow = row - dy[d]*4 + 1;	//시작점은 4방향전값 + 0부터시작했으므로 1더해줌
		fcol = col - dx[d]*4 + 1;	//시작점은 4방향전값 + 0부터시작했으므로 1더해줌
		return;
	}
	
	//다음방향도 이어진다면 호출
	if(cnt>=2&&arr[row+dy[d]][col+dx[d]]==who) dfs(row+dy[d], col+dx[d], cnt+1, who, d);
	
	//처음이라면 4방향 탐색
	if(cnt==1){
		for(int i=0;i<4;i++){
			if(arr[row+dy[i]][col+dx[i]]==who) dfs(row+dy[i], col+dx[i], cnt+1, who, i);
		}
	}
	
	return;
}


int main(){
	
	for(int i=0;i<19;i++){
		for(int j=0;j<19;j++){
			scanf("%d", &arr[i][j]);
		}
	}
	
	
	for(int i=0;i<19;i++){
		if(flag) break;
		for(int j=0;j<19;j++){
			if(arr[i][j]!=0) dfs(i, j, 1, arr[i][j], 0);
		}
	}
	
	if(flag) printf("%d\n%d %d", win, frow, fcol);
	else printf("0");
	
	return 0;
}