[백준 - 2615] 오목 - JAVA

문제

---

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

2615번: 오목

 

 

 

 

문제풀이

---

문제의 제한조건이 생각보다 까따로웠다. 연속적 5알이 되는 색이 이기는 구조인데, 검은색과 흰색이 동시에 이기는 경우도 없고, 두 곳 이상에서 이기는 경우도 없다. 제일 중요한 제한조건인 여섯알이 연속적으로 놓은 경우 이긴 것이 아니다. 라는 말이 있습니다.

여섯알이 될 경우 승부가 결정이 안나 0을 출력해야한다는 것으로 착각했지만 다른 곳에 오목이 되면 그 색이 이기는 문제였습니다.

 

*접근방법

일단 오목판은 19 * 19 고정인 배열 이기 때문에 시간복잡도는 크게 걱정하지 않아도 된다고 생각을 했습니다.

그리고 연속적으로 5알을 찾는다와, 각 이동하는 칸의 가중치가 1이기 때문에 Bfs 탐색을 생각했습니다.

 

탐색을 할 때 조건이 중요한데 갈 수 있는 방향은 8가지 입니다. 상하좌우 + 대각선4방향 하지만 모든 정점에서 8방향으로 탐색하게 된다면연속적인 5알 이상인 곳에서 어느 한 알에서 출발할 경우 5알이 될 때 와 5알 이상이 되는 경우를 처리하기가 매우 까다로워 집니다.

그래서 진행방향과 반대방향을 동시에 체크를 하면 위의 문제를 해결하면서 탐색이 가능해 집니다.

 

이 아이디어를 토대로 열심히 구현을 하면 됩니다. 참고로 방향 설정에 유의해야 합니다. 제가 구현한 코드는 +4를 하면 반대방향을 찾도록 구현을 했는데 다른 방법도 사용이 가능하니 더 좋은방법이 있으면 해당 방법으로 구현하셔도 됩니다.

 

 

 

 

소스코드

---

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

public class Main {
    static int n = 19;
    static int[][] map;
    static boolean[][] check;
    static boolean[][] winCheck;
    static final int[] dx = {-1, 0, -1, -1, 1, 0, 1, 1};
    static final int[] dy = {0, -1, -1, 1, 0, 1, 1, -1};
    static ArrayList<Node> list;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        map = new int[n][n];
        check = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!check[i][j] && map[i][j] != 0) {
                    if (bfs(i, j, map[i][j])) {
                        System.out.println(sb);
                        return;
                    }
                }
            }
        }

        System.out.println(0);
    }

    static boolean bfs(int x, int y, int color) {
        Queue<Node> q = new LinkedList<>();
        check[x][y] = true;
        q.add(new Node(x, y));

        winCheck = new boolean[n][n];
        winCheck[x][y] = true;

        while (!q.isEmpty()) {
            Node now = q.poll();
            x = now.x;
            y = now.y;

            for (int k = 0; k < 4; k++) {

                int count = 1;
                list = new ArrayList<>();
                list.add(new Node(x, y));

                if (k == 0) {
                    count += search(k, winCheck, now, color);
                    count += search(k + 4, winCheck, now, color);
                }

                if (k == 1) {
                    count += search(k, winCheck, now, color);
                    count += search(k + 4, winCheck, now, color);
                }

                if (k == 2) {
                    count += search(k, winCheck, now, color);
                    count += search(k + 4, winCheck, now, color);
                }

                if (k == 3) {
                    count += search(k, winCheck, now, color);
                    count += search(k + 4, winCheck, now, color);
                }

                if (count == 5) {
                    sb.append(color + "\n");
                    findPoint(list);
                    return true;
                }
            }
        }
        return false;
    }

    static int search(int k, boolean[][] winCheck, Node now, int color) {
        int count = 0;
        int nx = now.x + dx[k];
        int ny = now.y + dy[k];

        while(0 <= nx && nx < n && 0 <= ny && ny < n) {
            if (color == map[nx][ny] && !winCheck[nx][ny]) {
                winCheck[nx][ny] = true;
                list.add(new Node(nx, ny));
                nx += dx[k];
                ny += dy[k];
                count++;
            }else{
                break;
            }
        }
        return count;
    }

    static void findPoint(ArrayList<Node> list) {

        Collections.sort(list, (o1, o2) -> o1.y - o2.y);

        if (list.get(0).y == list.get(list.size() - 1).y) {
            Collections.sort(list, (o1, o2) -> o1.x - o2.x);
        }

        sb.append((list.get(0).x + 1) + " " +(list.get(0).y + 1));
    }

    static class Node{
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}