[99클럽 코테 스터디 14일차 TIL / 백준] 2615 - 오목 (브루트포스)

99클럽 코테스터디 14일차 TIL
KeyWord : 브루트포스

문제

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

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

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

입력

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

출력

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

 

---

 

풀이

브루트포스 문제라는 건 문제를 읽자마자 알 수 있었다. 하지만 오목을 판단하는 로직의 구현이 어려웠던 문제다.

여기서 어려운 부분은 연속된 돌이 6개 이상일 경우를 판단하는 것이다.

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

이 예시라면 1은 육목이고 2는 오목이 되지 않았으므로 0이 출력되어야 한다. 이는 당연하다.

하지만 우리는 모든 경우의 수를 살펴보아야 하므로, 반복문을 돌리며 (0,1)의 1을 지나고 많은 0들을 지나쳐 (1, 1)의 1에 도달했다.

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

(1, 1)을 시작점으로 오목인지 판단한다고 했을 때, (0, 1)의 돌을 고려하지 않고 6시 방향으로 이어진 돌들만 고려한다면 이를 오목으로 판정하게 될 수도 있다.

이 부분을 고려하지 않아 문제를 틀린 분들이 꽤 있을 듯하다.

나는 이것을 탐색하고자 하는 방향의 반대 방향에 같은 색의 돌이 존재하면, 육목으로 판단하는 식으로 로직을 구현했다. 즉, 6시 방향으로 탐색을 진행하기 전, 12시에 이미 자신과 같은 색의 돌이 존재한다면 육목으로 판단한다.

위 예제를 기준으로, (0, 1)에서 6시 방향으로 육목이 되었다고 판정이 되었으니 (1, 1)에서는 굳이 살펴보지 않게 해버리는 것이다.

또 이전의 나처럼 로직을 구현했을 경우 이러한 반례가 있을 수도 있다.

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

같은 색을 조건으로 두는 것이 아니라 방문하여 탐색을 진행한 적이 있는지로 조건을 주었다면, 이를 육목으로 판단할 수 있다.

나는 여기서 한 번 잘못 생각했다가 찾는데 1시간 30분이나 걸렸다. 탐색 문제니까 습관처럼 visited 배열 선언한 후 자연스럽게 사용해서 나타난 불상사였다.

 

 

오늘의 교훈
코드에 별 영향을 주지 않는다고 생각해도 불필요한 부분은 반드시 제거하자!

 

코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  

public class Main {  
    static int[][] board;  
    static StringBuilder sb = new StringBuilder();  

    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer stk;  

        board = new int[21][21];  

        for (int i = 0; i < 21; i++) {  
            board[0][i] = board[20][i] = board[i][0] = board[i][20] = 0;  
        }  

        for (int i = 1; i < 20; i++) {  
            stk = new StringTokenizer(br.readLine());  
            for (int j = 1; j < 20; j++) {  
                board[i][j] = Integer.parseInt(stk.nextToken());  
            }  
        }  

        for (int i = 1; i < 20; i++) {  
            for (int j = 1; j < 20; j++) {  
                if (board[i][j] == 1 || board[i][j] == 2) {  
                    search(i, j);  
                }  
            }  
        }  

        if(sb.isEmpty())  
            System.out.println(0);  
        else  
            System.out.println(sb);  
    }  

    private static void search(int startX, int startY) {  
        int[] dx = {0, 1, 1, 1};  
        int[] dy = {1, 1, 0, -1};  
        int currentColor = board[startX][startY];  

        int cnt;  
        boolean flag = true;  

        for (int i = 0; i < 4; i++) {  
            flag = true;  
            cnt = 1;  

            // 육목 체크  
            if (board[startX + dx[i] * -1][startY + dy[i] * -1] == currentColor) { 
                continue;  
            }  

            int nx = startX + dx[i];  
            int ny = startY + dy[i];  

            for (int j = 0; j < 4; j++) {  
                if(board[nx][ny] != currentColor) {  
                    flag = false;  
                    break;  
                }  

                nx += dx[i];  
                ny += dy[i];  
                cnt++;  
            }

            // 육목 체크  
            if(cnt == 5 && board[nx][ny] == currentColor) {  
                continue;  
            }  

            if(flag) {  
                sb.append(currentColor).append("\n");  

                int ansX = startX, ansY = startY;  
                for (int j = 0; j < 4; j++) {  
                    if(ansY > ansY + dy[i]) {  
                        ansX = ansX + dx[i];  
                        ansY = ansY + dy[i];  
                    } else {  
                        break;  
                    }  
                }  

                sb.append(ansX).append(" ").append(ansY);  
                break;  
            }  
        }  
    }  
}