[JAVA] 백준 2615

 

 

 

 

2615번: 오목

문제

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

풀이

이 문제를 풀면서 완전 탐색이란 무엇인가에 대해서 좀 더 깨달은 것 같다.

처음에는 그냥 오목의 승패 여부를 가르는 문제여서 쉽게 해결할 줄 알았으나 생각보다 많은 경우의 수가 존재했다.

내가 접근했던 방법

1. 이전에 풀었던 문제인 사탕 교환 문제 (https://g-db.tistory.com/entry/JAVA-백준-3085-완전탐색)에서 격자 형태의 탐색을 진행할 때 우측과 아래만 탐색하면 결과적으로 봤을 때 데칼코마니처럼 상, 하, 좌, 우 모두가 탐색되었다.
   • 그래서 이 문제도 해당 접근을 적용해서 우측 아래 인덱스부터 시작해서 올라오면서 상, 좌, 좌측 상단 대각선만 탐색하면서 올라가면 모든 경우의 수를 해결할 수 있을 것이라고 생각했다.
   • 하지만 나중에 알았지만 데칼코마니로 해봤을 때 우측 상단 대각선도 포함해야 모든 경우의 수를 탐색할 수 있었다…
2. 예제의 테스트케이스를 돌린 결과 잘 해결이 되서 답을 제출했지만 계속 틀렸다.
   • 다시 문제를 차근차근 읽어보았고 5개가 아닌 6개의 돌이 놓여있는 경우는 우승하는 경우가 아닌 것으로 판별해야 했다.

결과적으로 많은 시행착오가 있었고 이를 통해서 완전 탐색 문제에서는 경우의 수를 찾는 연습을 해야하고 경우의 수를 하나하나 작성해봐야겠다고 느꼈다.

📌 오목판을 2차원 배열로 입력받는다.

       A = new int[21][21];

       StringTokenizer st;
       for(int i=1; i<A.length-1; i++){
           st = new StringTokenizer(br.readLine(), " ");
           for(int j= 1; j<A.length-1; j++){
               A[i][j] = Integer.parseInt(st.nextToken());
           }
       }

이 경우에 나중에 배열 인덱스 예외를 방지하기 위해서 0번과 20번 인덱스를 추가로 만들어주었다.

📌 전체 경우의 수 탐색

       for(int i=A.length-2; i>=1 && answer == 0; i--){
           for(int j=A.length-2; j>= 1 && answer == 0; j--){
               if(A[i][j] != 0){
                    check(i, j, A[i][j]);
               }
           }
       }

가장 우측 하단인 19, 19부터 1, 1까지 돌면서 0이아닌 곳들만 경우의 수를 탐색해주었다.

📌 경우의 수 탐색

public static void check(int i, int j, int current){
        int count = 1;
        // 좌측
        for(int k=j-1; k>= 0 && k >=j-5; k--){
            if(current == A[i][k]){
                count++;
                locX = i;
                locY = k;
            }else {
                break;
            }
        }
        if(count == 5 && A[i][j+1] != current && A[locX][locY-1] != current) {
            answer = current;
            return;
        }
        // 상단
        count = 1;
        for(int k=i-1; k>= 0 && k >= i-5; k--){
            if(current == A[k][j]){
                count++;
                locX = k;
                locY = j;
            }else {
                break;
            }
        }
        if(count == 5 && A[i+1][j] != current && A[locX-1][locY] != current) {

            answer = current;
            return;
        }

        // 좌측 상단 대각선
        count = 1;
        int x = i-1; int y = j-1;
        while (x >= 0 && y >= 0 && x >=j-5 && y >=i-5){
            if(current == A[x][y]){
                count++;
                locX = x--;
                locY = y--;
            }else {
                break;
            }
        }
        if(count == 5 && A[i+1][j+1] != current && A[locX-1][locY-1] != current){
            answer = current;
            return;
        }count = 1;

        // 우측 상단 대각선
        x = i-1; y = j+1;
        while (x >= 0 && y < A.length-1 && x >= i-5 && y <= j+5){
            if(A[x][y] == current){
                count++;
                locX = x--;
                locY = y++;
            }else{
                break;
            }
        }
        // 우측 상단의 경우 가장 좌측 돌의 좌표는 시작점이 된다.
        if(count == 5 && A[i+1][j-1] != current && A[locX-1][locY+1] != current){
            locX = i;
            locY = j;
            answer = current;
        }

    }

4가지 경우로 살펴보자.

좌측 (좌측, 좌측 상단 대각선, 상단은 유사하다.)

                 // 좌측        
        int count = 1;
        for(int k=j-1; k>= 0 && k >=j-5; k--){
            if(current == A[i][k]){
                count++;
                locX = i;
                locY = k;
            }else {
                break;
            }
        }
        if(count == 5 && A[i][j+1] != current && A[locX][locY-1] != current) {
            answer = current;
            return;
        }

count : 연속되는 돌의 수를 체크한다.

현재 좌표에서 왼쪽으로 5번째 좌표까지 체크한다.

가장 마지막 돌의 좌표를 알아야하기 때문에 locX, locY를 계속 갱신해준다.

마지막으로 if문에서 현재 연속되는 돌이 5개 이상인지 체크해주기 위해 마지막 돌에서 좌측, 첫 번째 시작 돌에서 우측 돌을 체크해서 같지 않은 경우에만 정답으로 인정한다.

우측 상단 대각선

        // 우측 상단 대각선
        x = i-1; y = j+1;
        while (x >= 0 && y < A.length-1 && x >= i-5 && y <= j+5){
            if(A[x][y] == current){
                count++;
                locX = x--;
                locY = y++;
            }else{
                break;
            }
        }
        // 우측 상단의 경우 가장 좌측 돌의 좌표는 시작점이 된다.
        if(count == 5 && A[i+1][j-1] != current && A[locX-1][locY+1] != current){
            locX = i;
            locY = j;
            answer = current;
        }

우측 상단 대각선의 경우에는 좌측에서 우측으로 가는 경우이기 때문에 정답 좌표를 시작점으로 갱신해주는 과정이 추가된다.

📌 전체 코드

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

class Main {
    static int[][] A;
    static int answer = 0;
    static int locX = 0;
    static int locY = 0;
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       A = new int[21][21];

       StringTokenizer st;
       for(int i=1; i<A.length-1; i++){
           st = new StringTokenizer(br.readLine(), " ");
           for(int j= 1; j<A.length-1; j++){
               A[i][j] = Integer.parseInt(st.nextToken());
           }
       }

       for(int i=A.length-2; i>=1 && answer == 0; i--){
           for(int j=A.length-2; j>= 1 && answer == 0; j--){
               if(A[i][j] != 0){
                    check(i, j, A[i][j]);
               }
           }
       }
       System.out.println(answer);
       if(answer != 0){
           System.out.println((locX) + " " +( locY));
       }

    }

    public static void check(int i, int j, int current){
        int count = 1;
        // 좌측
        for(int k=j-1; k>= 0 && k >=j-5; k--){
            if(current == A[i][k]){
                count++;
                locX = i;
                locY = k;
            }else {
                break;
            }
        }
        if(count == 5 && A[i][j+1] != current && A[locX][locY-1] != current) {
            answer = current;
            return;
        }
        // 상단
        count = 1;
        for(int k=i-1; k>= 0 && k >= i-5; k--){
            if(current == A[k][j]){
                count++;
                locX = k;
                locY = j;
            }else {
                break;
            }
        }
        if(count == 5 && A[i+1][j] != current && A[locX-1][locY] != current) {

            answer = current;
            return;
        }

        // 좌측 상단 대각선
        count = 1;
        int x = i-1; int y = j-1;
        while (x >= 0 && y >= 0 && x >=j-5 && y >=i-5){
            if(current == A[x][y]){
                count++;
                locX = x--;
                locY = y--;
            }else {
                break;
            }
        }
        if(count == 5 && A[i+1][j+1] != current && A[locX-1][locY-1] != current){
            answer = current;
            return;
        }count = 1;

        // 우측 상단 대각선
        x = i-1; y = j+1;
        while (x >= 0 && y < A.length-1 && x >= i-5 && y <= j+5){
            if(A[x][y] == current){
                count++;
                locX = x--;
                locY = y++;
            }else{
                break;
            }
        }
        // 우측 상단의 경우 가장 좌측 돌의 좌표는 시작점이 된다.
        if(count == 5 && A[i+1][j-1] != current && A[locX-1][locY+1] != current){
            locX = i;
            locY = j;
            answer = current;
        }

    }

}

결과