[BOJ] 2615 오목 (Java)

https://www.acmicpc.net/problem/2615

 

<초기 아이디어>

처음에 문제 읽고 설계했던 방식은 다음과 같다.

1. 모든 바둑돌의 좌표를 구조체를 만들어 바둑돌 색상과 함께 큐에 저장한다.

2. 하나씩 꺼내면서 dfs로 8방 탐색을 한다.

3. 범위를 벗어나거나 방문했거나 다른 바둑돌 색상을 만나지 않고, 같은 바둑돌 색이면 cnt+1을 한다.

4. 범위를 벗어나거나 방문했거나 다른 바둑돌 색상을 만나면 cnt를 확인해서 5이면 그 때의 시작 좌표를 출력한다.

하지만 2-3%에서 틀렸고, 좌표를 찍어보며 수정하는 과정에서 엄청나게 많은 허점이 있음을 깨달았다.

 

<문제>

1번 허점)

그냥 큐에 저장하면 안됐다. 처음엔 위에서 아래로 배열을 탐색하기 때문에 조건을 만족한다고 생각했는데,

반례를 보면서 만약 바둑돌이 왼쪽 아래에서 오른쪽 위로 향하는 경우 아래 행이 시작좌표여야 함을 깨달았다.

-> 따라서 이를 우선순위큐로 변경하고, 행을 우선 오름차순 열 오름차순으로 정렬하도록 하였다.

 

2번 허점)

일단 8방을 굳이 할 필요가 없었다. 이미 지나온 바둑돌들은 확인하지 않아도 되니,

오른쪽 위 대각선 / 오른쪽 / 오른쪽 아래 대각선 / 아래 총 4방 탐색만 해도 된다.

또한, 시작 좌표에서 4방으로 탐색을 돌리면 안됐다.

이렇게 하면 제한 조건을 만났을 경우 리턴하면서 다른 방향으로 변경하기에 한 방향으로만 탐색한 결과를 알수 없게 된다.

즉, 오른쪽 - 오른쪽 - (제한 조건 만나서 리턴) - 왼쪽 - .. 이런식으로 가게 된다.

-> 따라서 이를 dfs 시작 전에 각 방향을 들고 탐색하도록 변경해주었다.

 

그리고 가장 나를 힘들게 했던 문제는 바로 6목 이상인 경우를 확인해주는 과정이었는데..

6목 이상인 경우를 제외하기 위해 이전에 방문했던 같은 색상의 오목 좌표를 방문처리해서 이후에는 가지 않도록 하였더니

다른 시작좌표에서 해당 좌표를 포함해 5목인 경우를 찾을 수 없었고,

다시 이를 해결하기위해 방문처리를 빼니 또 다시 6목 이상인 경우를 제외할 수가 없었다.

이런 아이러니로 인해 8%와 13% 틀렸습니다를 반복했다.. (하도 많이 봐서 외워버림)

 

몇번의 시도 끝에 이 문제를 확인하고 내린 해결책은.. 6목 이상인 경우 마지막 좌표에 체크를 하는 배열을 만들어서

다른 시작 좌표로 5목 이더라도 마지막 좌표가 이전에 6목 이상으로 체크됐던 좌표라면 제외시키는 것이었다. (이 좌표로 끝나면 6목인 좌표다~)

(예로, 1-2-3-4-5-6 으로 연결되어 있었다면, 1에서 시작해서 6에 도달했을 때 체크해두고, 2에서 시작해서 6도착(오목)하더라도 제외)

 

이렇게해서 통과하긴 했지만,, 너무 주먹구구식으로 푼 거 같아서.. 이 문제는 그냥 완탐으로 푸는 게 훨 나았을 거 같다는 생각이 든다 ㅠㅠ

 

< 최종 아이디어>

1. 모든 바둑돌의 좌표를 구조체를 만들어 바둑돌 색상과 함께 우선순위 큐에 저장한다.

2. 우선순위 큐를 행과 열에 대해 오름차순으로 정렬한다.

3. 하나씩 꺼내면서 각 시작좌표마다 4방 탐색을 위해 하나의 방향을 들고 dfs로 탐색한다.

4. 범위를 벗어나거나 방문했거나 다른 바둑돌 색상을 만나지 않고, 같은 바둑돌 색이면 cnt+1을 한다.

5-1. 범위를 벗어나거나 방문했거나 다른 바둑돌 색상을 만나면 cnt를 확인해서 6이상이면 마지막 바둑돌 좌표를 not 배열에 체크하고,

5-2. cnt가 5이고 마지막 바둑돌의 좌표가 not에 체크되어 있지 않으면 그 때의 시작 좌표를 출력한다.

 

<제출코드>

package Study.Week04;

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

public class Day25_BONUS_BOJ_2615_오목 {
    static class Point implements Comparable<Point> {
        int color;
        int x, y;
        int cnt;
        Point(int color, int x, int y, int cnt){
            this.color = color;
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
        @Override
        public int compareTo(Point o){
            int tmp = this.y - o.y;
            if(tmp == 0) tmp = this.x - o.x;
            return tmp;
        }
    }

    static boolean flag;
    static int[][] arr;
    static int[] dx = {-1, 0, 1, 1};
    static int[] dy = {1, 1, 1, 0};
    static boolean[][] visited;
    static boolean[][] not;
    static PriorityQueue<Point> pq;
    static StringBuilder sb;

    public static void dfs(int x, int y, int color, int d, int cnt){
        int nx = x + dx[d];
        int ny = y + dy[d];
        int ncnt = cnt + 1;
        // 탐색 제외 조건
        if(nx<0 || ny<0 || nx>=19 || ny>=19 || visited[nx][ny] || arr[nx][ny]!=color) {
            // 6목 이상인 경우 마지막 바둑알 좌표
            if(ncnt > 5) not[x][y] = true;
            // 같은 색의 바둑알이 5개인 경우
            if(ncnt == 5) {
                // 6목이 아닌 경우
                if(!not[x][y]) flag = true;
            }
            return;
        }
        dfs(nx, ny, color, d, ncnt);
        if(flag) return;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        sb = new StringBuilder();
        arr = new int[19][19];
        pq = new PriorityQueue<>();
        for(int i=0; i<19; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<19; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
                // 검은색 또는 흰색 바둑알 위치 저장
                if(arr[i][j] == 1 || arr[i][j] == 2) pq.add(new Point(arr[i][j], i, j, 0));
            }
        }
        not = new boolean[19][19];
        while(!pq.isEmpty()){
            Point p = pq.poll();
            visited = new boolean[19][19];
            visited[p.x][p.y] = true;
            for(int d=0; d<4; d++){
                dfs(p.x, p.y, p.color, d, p.cnt);
                if(flag) {
                    sb.append(p.color + "\n" + (p.x+1) + " " + (p.y+1));
                    System.out.println(sb.toString());
                    return;
                }
            }
        }
        System.out.println(0);
    }
}

 

8% - 13% 틀렸습니다의 무한 반복끝에 일궈낸 결과,,ㅠㅠ