[백준/boj] 2615: 오목 (Java) / 브루트포스 / 구현

문제

2615번: 오목

풀이

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int[][] map = new int[19][19];
	static int[] dx = { 0, 1, -1, 1, 0, -1, 1, -1 };
	static int[] dy = { 1, 1, 1, 0, -1, -1, -1, 0 };
	static boolean[][][] visited = new boolean[19][19][4];
	static Deque<int[]> deque = new ArrayDeque();

	public static void main(String[] args) throws Exception {
		for (int i = 0; i < 19; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 19; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 1 || map[i][j] == 2)
					deque.add(new int[] { i, j });
			}
		}

		while (!deque.isEmpty()) {
			int[] pos = deque.poll();
			int x = pos[0];
			int y = pos[1];

			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (!isRange(nx, ny)) continue;
				if (!visited[nx][ny][i] && countFive(nx, ny, i, map[x][y])) {
					if(!isRange(x+dx[i+4], y+dy[i+4])) {
						System.out.println(map[x][y]);
						System.out.print((x+1) + " " + (y+1));
						return;
					}
					if(isRange(x+dx[i+4], y+ dy[i+4]) && map[x + dx[i+4]][y + dy[i+4]] != map[nx][ny]) {
						System.out.println(map[x][y]);
						System.out.print((x+1) + " " + (y+1));
						return;
					}
				}
			}
		}
		System.out.println(0);
	}

	private static boolean countFive(int x, int y, int dir, int color) {
		if(color == 0) return false;
		int cnt = 1;
		while (map[x][y] == color) {
			cnt++;
			visited[x][y][dir] = true;
			x += dx[dir];
			y += dy[dir];
		}
		return cnt == 5 ? true : false;
	}

	private static boolean isRange(int nx, int ny) {
		return nx < 0 || nx >= 19 || ny < 0 || ny >= 19 ? false : true;
	}
}

 

 

1. 맵 정보를 받아올 때, 검은 돌(1) 이거나 흰 돌(2)이면 deque에 삽입했다. (0,0) (0,1) (0,2) ••• (1,0) (1,1) (1,2) ••• (18,18) 의 순서로 담아온다. 즉 가장 상단의 왼쪽 돌부터 오목인지 아닌지를 판단한다. 이는 오목인지 탐색할 방향과 관련이 있다.

static int[] dx = { 0, 1, -1, 1, 0, -1, 1, -1 };
static int[] dy = { 1, 1, 1, 0, -1, -1, -1, 0 };

2. deque가 빌 동안 dfs 탐색을 했다.

• visited[nx][ny][i] : i방향으로 탐색한 적이 있는지를 확인한다. (i방향으로 탐색한 적이 있었는데 프로그램이 종료 안됐다는 것은 i방향에서는 오목이 아니었다는 것을 의미한다. 탐색한 적이 없을때 countFive함수를 실행한다.
• countFive(x, y, dir, color)
  • nx, ny 좌표를 x, y로 받아오고, 탐색할 방향은 dir, map[nx][ny] 이전의 바둑돌 색(map[x][i])은 color로 받아온다.
    • map[x][y] 가 color 와 다르다는 것은 이전 바둑돌 색과 탐색할 바둑돌의 색이 다른것을 의미하므로 while문을 돌지 않고 false를 반환한다.
    • 같은 색이라면 색이 달라질때까지 dir방향으로 옮기면서 count 를 1씩 증가시킨다.
    • cnt가 5면 일단 탐색한 방향으로는 오목의 조건을 충족했으므로 true를 반환한다.
• i 방향으로 처음 탐색했고 map[x][y] 부터 i 방향으로 5개의 바둑돌이 같은 색이었다면 이제 두가지를 확인하면 된다. 
  • 반대 방향(i+4 -> 위 그림 참고)이 range를 벗어나면 무조건 오목이다. (x, y가 오목의 시작돌이었음을 의미)
  • 반대 방향의 바둑돌이 range안이고 map[x][y]와 다른 색이라는 것은 오목임을 의미한다 !
  • 위 두 상황이면 그 돌의 색과 좌표 (0,0 ~ 18,18 이므로 +1 해서 출력)를 출력하면 끝이다.

3. deque가 다 비었을때 프로그램이 종료되지 않았다는 것은 오목이 존재하지 않는다는 것이므로 0을 출력한다.