백준 2615 <오목>

DFS를 사용하는 완전 탐색이다.

5목이 아닌 6목 그 이상이 되는 예외 상항만 처리해주면 되기 때문에 생각보다 어려운 문제는 아니었다.

 

다만 문제를 해결하면서 시간 복잡도를 최소화하는 방법을 찾는데에 집중했던 문제였다.

 

시간을 줄이기 위해 이문제에서 사용된 방법은 바둑돌이 놓인 지점에서 

이렇게 8방향을 탐색하는 것이 아닌 5목이 된다면 출력을 하게될 바둑돌의 좌표는 

가장 왼쪽 그리고 가장 위쪽에 있는 좌표이기 때문에

이렇게 4방향만 검사를 해주게 되면 출력할 좌표를 쉽게 구할 수 있고 시간을 간편화 할 수 있다.

 

총 20*20의 맵이기 때문에 2중 for문을 사용해주었고 그 지점이 흑돌 또는 백 돌일 때 탐색을 실행시켜주었다.

각 돌의 지점에서 시작점을 포함해 5번을 이동하면서 이동한 지점의 돌이 같을경우 빨간 네모 부분을 실행해주게 되고 

if문을 통해 시작점 이전의 돌과 이후의 돌이 시작점과 색이 다르다면 결과를 출력하게 되는 코드이다.

이 예외사항을 생각해서 해결해주게 된다면 쉽게 해결할 수 있는 문제이다.

 

전체 코드

import java.util.Scanner;

public class Main{
	static int map[][] = new int[19][19], dir[][] = { { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 } };// 오른쪽대각선,오른쪽,아래대각선,아래
	static int result = 0, resultx = -1, resulty = -1;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		for (int i = 0; i < 19; i++) {
			for (int j = 0; j < 19; j++) {
				map[i][j] = kb.nextInt();
			}
		}
		for (int i = 0; i < 19; i++) {
			for (int j = 0; j < 19; j++) {
				if (map[i][j] == 1 || map[i][j] == 2)
					go(i, j);
				if (result != 0) {
					System.out.println(result);
					System.out.println(resultx + " " + resulty);
					return;
				}
			}
		}
		System.out.println(result);
	}

	public static void go(int x, int y) {
		for (int i = 0; i < 4; i++) {
			int x1 = x;
			int y1 = y;
			boolean s = true;
			for (int j = 0; j < 5; j++) {
				if (x1 < 0 || x1 >= 19 || y1 < 0 || y1 >= 19 || map[x][y] != map[x1][y1]) {
					s = false;
					break;
				}
				x1+=dir[i][0];
				y1+=dir[i][1];
			}
			if (s == true) {
				if((x1 < 0 || x1 >= 19 || y1 < 0 || y1 >= 19 || map[x][y] != map[x1][y1])
                   &&(x-dir[i][0] < 0 || x-dir[i][0] >= 19 || y-dir[i][1] < 0 || y-dir[i][1] >= 19 
                      || map[x][y] != map[x-dir[i][0]][y-dir[i][1]])) {
				result = map[x][y];
				resultx = x+1;
				resulty = y+1;
				}
			
			}

		}
	}

}