[백준] 2615 오목 - 완전탐색 (DFS) JAVA

https://www.acmicpc.net/problem/2615

2615번: 오목

코드설명

DFS를 활용하여 완전탐색을 진행했습니다.

이 문제 같은경우 문제의 뼈대를 구현하는 것은 어렵지 않습니다.

가장 신경서야할 부분은 오목이 아닌 육모 이상인 경우에를 신경써야합니다.

 

(0,0) 부터 (18,18)까지 모든 경우를 돌면서 dx, dy 를 선언했습니다. 여기서 dx, dy는 우상대각, 우측, 우하대각, 하측 이렇게 4가지 경우를 두고서 완전탐색을 돌립니다. 여기서 우상대각에서 시계방향으로 4가지 방향으로 탐색하는 이유는

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

라는 조건이 있어서 그렇습니다.

위의 구조 안에서 완전탐색을 만약에 성공했다고 합니다. 그렇다면, 이제 오목 에서 다음 칸 한가지를 더 가서 해당 칸 또한 연결되어있는지 확인합니다.그리고서 아직도 오목이라면, 첫 시작점으로 가서 해당 칸의 전 칸으로 이동하여 연결되었는지 확인합니다.예시를 들면 아래의 예시에서 첫번째 열에 1이 8개 있으므로, 위의 조건들을 구현해야한다는것을 알 수 있습니다.

1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0

 

처음에 제가 틀렸던 경우는 level == 5가 되었을때, 오른쪽 하단만 계산했기 때문입니다. 해당 방향의 반대방향도 검사해야합니다. 

또, dfs에서 level은 첫 시작과 동시에 +1 이므로 dfs 시작시 level = 1 이라는 Parameter로 넘겨줍니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
//만약 5목이 완성되었다면 6목이있는지 확인하고,
//만약 해당 조건도 완성되었다면, 5목의 입장에서 반대방향의 오목 한칸이 존재하는지 확인해야함
 
public class Main {
	
	public static int N;
	public static int[][] map = new int[19][19];
	public static boolean[][] visited = new boolean[19][19];
//	(0,0)부터 탐색하니, 우상대각, 오른쪽, 우하대각, 아래쪽  4가지에, 좌하대각, 왼쪽, 좌상대각, 위쪽, 
//	이렇게 설계한 이유는,  연속된 다섯 개의 바둑알 중에서 가장 왼쪽에 있는 바둑알 이라는 조건과 세로측에서는 맨 위의 바둑알이라는 조건을 고려
	public static int[] dx = {-1, 0, 1, 1, 1, 0, -1, -1};
	public static int[] dy = {1, 1, 1, 0, -1, -1, -1, 0};
	public static int result = 0;
	public static boolean flag = false; //6목인지 확인하기 위한 flag
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	
    	for(int i=0;i<19;i++) {
    		StringTokenizer st = new StringTokenizer(br.readLine());	
    		for(int j=0;j<19;j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	
    	for(int i=0;i<19;i++) {
    		
    		for(int j=0;j<19;j++) {
    			if(map[i][j] != 0) {
    				
    				for(int dir=0;dir<4;dir++) {
    					flag = false;
    					simulate(new Node(i, j, map[i][j]), 1, dir);
    					
    					
    					//6목이 아닌경우에 넘어옴
    					if(flag == false) {
    						//반대방향에서 1칸 확인해야함, +4 한값이 해당 방향의 반대값입니다
    			    		int nr = i + dx[dir + 4];
    			    		int nc = j + dy[dir + 4];
    			    		int color = map[i][j];
    			    		
    			    		//만약 다음칸으로 이동해도 범위를 벗어날시 성공한것으로 처리가능.
    			    		if(nr >= 0 && nr < 19 && nc >= 0 && nc < 19) {
        			    		//만약 다음칸이 같은색이라면 6목이므로 실패처리하기 위해 flag = true
        			    		if(map[nr][nc] == color) {
        			    			result = 0;
        			    		}
    			    		}
    			    		
    						if(result != 0) {
    							System.out.println(result);
    							System.out.println((i+1)+" "+(j+1));
    							return ;
    						}
    					}
    				
    				}
    			}	
    		}	
    	}
    	System.out.println(result);
    	
 
		
    }
    
    public static void simulate(Node start, int level, int dir) {
    	if(level == 5) {
    		int nr = start.r + dx[dir];
    		int nc = start.c + dy[dir];
    		int color = start.color;
    		
    		//만약 다음칸으로 이동해도 범위를 벗어날시 성공한것으로 처리가능.
    		if(nr < 0 || nr >= 19 || nc < 0 || nc >= 19) {
    			result = start.color;
    			return ;
    		}    		
    		
    		//만약 다음칸이 같은색이라면 6목이므로 실패처리하기 위해 flag = true
    		if(map[nr][nc] == color) {
    			flag = true;
    			return ;
    		}
    		
    		//다음것 존재하는지 확인하여 flag = false로 유지
    		if(map[nr][nc] != color) {
    			result = start.color;
    			return ;
    		}
    	}
    	
		int nr = start.r + dx[dir];
		int nc = start.c + dy[dir];
		int color = start.color;
		if(nr < 0 || nr >= 19 || nc < 0 || nc >= 19) return ;
		if(map[nr][nc] != color) return ;
		if(visited[nr][nc] == true) return ;
		
		visited[nr][nc] = true;
		simulate(new Node(nr, nc, color), level + 1, dir);
		if(flag == false) {
			visited[nr][nc] = false;
		}
		
    }
 
}
 
 
class Node{
	int r;
	int c;
	int color;
	public Node(int r, int c, int color) {
		this.r=r;
		this.c=c;
		this.color = color;
	}
}