[Baekjoon] 오목

👀 문제 설명

문제

오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙는다.

위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림은 검은색이 이긴 경우이다. 하지만 여섯 알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다.

입력으로 바둑판의 어떤 상태가 주어졌을 때, 검은색이 이겼는지, 흰색이 이겼는지 또는 아직 승부가 결정되지 않았는지를 판단하는 프로그램을 작성하시오. 단, 검은색과 흰색이 동시에 이기거나 검은색 또는 흰색이 두 군데 이상에서 동시에 이기는 경우는 입력으로 들어오지 않는다.

 

입력

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

 

출력

첫줄에 검은색이 이겼을 경우에는 1을, 흰색이 이겼을 경우에는 2를, 아직 승부가 결정되지 않았을 경우에는 0을 출력한다. 검은색 또는 흰색이 이겼을 경우에는 둘째 줄에 연속된 다섯 개의 바둑알 중에서 가장 왼쪽에 있는 바둑알(연속된 다섯 개의 바둑알이 세로로 놓인 경우, 그 중 가장 위에 있는 것)의 가로줄 번호와, 세로줄 번호를 순서대로 출력한다.

 

예제 입력 1

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 1 2 0 0 2 2 2 1 0 0 0 0 0 0 0 0 0 0

0 0 1 2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0

0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 1 2 2 0 0 0 0 0 0 0 0 0 0 0 0

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

0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

 

예제 출력 1

1

3 2

 

✍🏻풀이

바둑판 정보를 받을 때, 검은 돌(1)이거나 흰 돌(2)이라면 큐에 삽입한다.

이겼을 경우, 가장 왼쪽에 있는 바둑알 or 세로로 놓인 경우, 가장 위에 있는 바둑알의 위치를 출력해야 하기 때문에, (0, 0), (0, 1), .. (1, 0), (1, 1), ... (18, 18)의 순서로 담아왔다.

그리고 큐에서 하나씩 꺼내어 같은 색의 바둑알이 연속으로 5개인지 확인한다. 이 때, dx와 dy 변수를 사용한다.

dx와 dy 변수는 4개씩 사용한다. 아래 코드를 보면, 먼저 한쪽 방향으로 5개가 있는지 검사하고, 그 반대 방향을 검사하기 때문이다.

 

board의 크기를 20 20으로 했었는데, ArrayIndexOutOfBounds 오류가 계속 나서 21로 바꿨더니 정답이 되었ㄴ다..! 이유를 잘 모르겠따...

 

코드

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

// 오목(https://www.acmicpc.net/problem/2615)

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int[][] board = new int[21][21];
	static int[] dx = { 1, 0, -1, 1, -1, 0, 1, -1 }; 
	static int[] dy = { 1, 1, 1, 0, -1, -1, -1, 0 }; 
	static Queue<int[]> queue = new LinkedList<>(); // 큐 사용
	static boolean[][][] visited = new boolean[21][21][4];

	public static void main(String[] args) throws IOException {
		// input
		for (int i = 1; i <= 19; i++) {
			st = new StringTokenizer(br.readLine());
			
			for (int j = 1; j <= 19; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
				
				if (board[i][j] == 1 || board[i][j] == 2)
					queue.add(new int[] { i, j }); // 큐에 배열 객체 { i, j } 추가
			}
		}

		// solve
		while (!queue.isEmpty()) {
			int[] cur = queue.poll(); // 큐에서 첫번째 값 반환하고 제거 - poll
			int curX = cur[0];
			int curY = cur[1];
			
			for (int dir = 0; dir < 4; dir++) {
				int nextX = curX + dx[dir];
				int nextY = curY + dy[dir];
				
				if (nextX < 1 || nextX > 19 || nextY < 1 || nextY > 19)
					continue;
				
				// 1. (nextX, nextY) 위치에서 dir 방향으로 방문한 적이 없고,
				// 2. nextX, nextY에서 dir 방향으로 (curX, curY) 포함 연속된 돌이 5개일 경우
				if (!visited[nextX][nextY][dir] && countFive(nextX, nextY, dir, board[curX][curY])) {
					// 반대편 확인
					int reverseX = curX + dx[dir + 4];
					int reverseY = curY + dy[dir + 4];
					
					// 반대편이 범위를 넘어갈 경우, 연속된 같은 색의 바둑알은 5개라는 뜻이므로, 현재 색이 이긴다.
					if (reverseX < 1 || reverseX > 19 || reverseY < 1 || reverseY > 19) {
						System.out.println(board[curX][curY]);
						System.out.println(curX + " " + curY);
						return;
					}
					
					// 반대편이 보드이고, 다른색의 바둑알일 경우, 연속된 같은 색의 바둑알은 5개라는 뜻으로, 현재 색이 이긴다.
					if ((reverseX >= 1 && reverseX <= 19 && reverseY >= 1 && reverseY <= 19) && board[reverseX][reverseY] != board[nextX][nextY]) {
						System.out.println(board[curX][curY]);
						System.out.println(curX + " " + curY);
						return;
					}
				}
			}
		}
		
		// queue에 아무것도 없을 때까지 while문이 돌면, 비겼다는 뜻이므로 0을 출력한다.
		System.out.println(0);
	}

	// (x, y) 위치부터 dir 방향으로 같은 색의 연속된 돌이 5개인지 판단하는 함수
	private static boolean countFive(int x, int y, int dir, int color) {
		if (color == 0) return false;
		
		int count = 1;
		while (board[x][y] == color) {
			count++;
			visited[x][y][dir] = true;
			x += dx[dir];
			y += dy[dir];
		}
		
		return (count == 5) ? true : false;
	}
}