[JAVA] BOJ 백준 2615번 - 오목

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

---

2. 내가 푼 방법

전형적인 BFS 문제이다. 3차원 배열인 visit을 선언해 이미 방문한 적 있는 위치일 경우에는 뛰어넘도록 코드를 작성했다.

 

상+하, 좌+우, 대각선 2개로 뻗어나가는 방향을 합쳐서 카운팅해야하기 때문에, bfs 함수 안에서 cntArr 배열에 각 방향으로 뻗어나가는 위치를 카운팅해줬다. cntArr 배열을 PriorityQueue로 선언해 준 이유는 x가 가장 작은 위치(x가 같을 경우 y가 가장 작은 위치)를 반환해주기 위해서이다.

 

큐가 돌아갈 때 direction은 상/하/좌/우/대각선 4개 포함해서 0~7을 갖고 있고, oneDirection은 상하/좌우/대각선 2개를 포함해서 0~3을 갖고 있다. direction을 통해 oneDirection을 구해주는 getOneDirection함수를 작성했다.

public static void solution() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (arr[i][j] != 0) bfs(i, j);
        }
    }
}

public static void bfs(int i, int j) {
    Queue<Tuple> queue = new LinkedList<>();
    for (int dir = 0; dir < 8; dir++) {
        queue.add(new Tuple(i, j, dir));
    }

    PriorityQueue<Tuple>[] cntArr = new PriorityQueue[4];
    for (int q = 0; q < 4; q++) {
        cntArr[q] = new PriorityQueue<>();
        cntArr[q].add(new Tuple(i, j, q));
    }

    while (!queue.isEmpty()) {
        Tuple tuple = queue.poll();
        int x = tuple.x;
        int y = tuple.y;
        int direction = tuple.direction;
        int oneDirection = getOneDirection(direction);

        if (x <= 0 || y <= 0 || x > N || y > N) continue;
        if (visit[x][y][oneDirection]) continue;
        if (arr[i][j] != arr[x][y]) continue;

        if (x != i || y != j) {
            cntArr[oneDirection].add(new Tuple(x, y, direction));
        }

        queue.add(move(x, y, direction));
    }

    for (PriorityQueue<Tuple> cnt : cntArr) {
        if (cnt.size() == 5) {
            win = arr[i][j];
            Tuple first = cnt.poll();
            winSite[0] = first.x;
            winSite[1] = first.y;
            visit[first.x][first.y][getOneDirection(first.direction)] = true;
        }

        for (Tuple t : cnt) {
            visit[t.x][t.y][getOneDirection(t.direction)] = true;
        }
    }
}

public static Tuple move(int x, int y, int direction) {
    if (direction == 0) return new Tuple(x-1, y, direction);
    else if (direction == 1) return new Tuple(x-1, y+1, direction);
    else if (direction == 2) return new Tuple(x, y+1, direction);
    else if (direction == 3) return new Tuple(x+1, y+1, direction);
    else if (direction == 4) return new Tuple(x+1, y, direction);
    else if (direction == 5) return new Tuple(x+1, y-1, direction);
    else if (direction == 6) return new Tuple(x, y-1, direction);
    else return new Tuple(x-1, y-1, direction);
}

public static int getOneDirection(int direction) {
    if (direction == 0 || direction == 4) return 0;
    else if (direction == 1 || direction == 5) return 1;
    else if (direction == 2 || direction == 6) return 2;
    else return 3;
}

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B2615.java

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

class Main {
    static int N = 19;
    static int[][] arr;
    static int win;
    static int[] winSite;
    static boolean[][][] visit;

    public static void main (String[] args) throws IOException {
        init();
        solution();
        print();
    }

    public static void solution() {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (arr[i][j] != 0) bfs(i, j);
            }
        }
    }

    public static void bfs(int i, int j) {
        Queue<Tuple> queue = new LinkedList<>();
        for (int dir = 0; dir < 8; dir++) {
            queue.add(new Tuple(i, j, dir));
        }

        PriorityQueue<Tuple>[] cntArr = new PriorityQueue[4];
        for (int q = 0; q < 4; q++) {
            cntArr[q] = new PriorityQueue<>();
            cntArr[q].add(new Tuple(i, j, q));
        }

        while (!queue.isEmpty()) {
            Tuple tuple = queue.poll();
            int x = tuple.x;
            int y = tuple.y;
            int direction = tuple.direction;
            int oneDirection = getOneDirection(direction);

            if (x <= 0 || y <= 0 || x > N || y > N) continue;
            if (visit[x][y][oneDirection]) continue;
            if (arr[i][j] != arr[x][y]) continue;

            if (x != i || y != j) {
                cntArr[oneDirection].add(new Tuple(x, y, direction));
            }

            queue.add(move(x, y, direction));
        }

        for (PriorityQueue<Tuple> cnt : cntArr) {
            if (cnt.size() == 5) {
                win = arr[i][j];
                Tuple first = cnt.poll();
                winSite[0] = first.x;
                winSite[1] = first.y;
                visit[first.x][first.y][getOneDirection(first.direction)] = true;
            }

            for (Tuple t : cnt) {
                visit[t.x][t.y][getOneDirection(t.direction)] = true;
            }
        }
    }

    public static Tuple move(int x, int y, int direction) {
        if (direction == 0) return new Tuple(x-1, y, direction);
        else if (direction == 1) return new Tuple(x-1, y+1, direction);
        else if (direction == 2) return new Tuple(x, y+1, direction);
        else if (direction == 3) return new Tuple(x+1, y+1, direction);
        else if (direction == 4) return new Tuple(x+1, y, direction);
        else if (direction == 5) return new Tuple(x+1, y-1, direction);
        else if (direction == 6) return new Tuple(x, y-1, direction);
        else return new Tuple(x-1, y-1, direction);
    }

    public static int getOneDirection(int direction) {
        if (direction == 0 || direction == 4) return 0;
        else if (direction == 1 || direction == 5) return 1;
        else if (direction == 2 || direction == 6) return 2;
        else return 3;
    }

    public static class Tuple implements Comparable<Tuple>{
        int x;
        int y;
        int direction;

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

        @Override
        public int compareTo(Tuple t) {
            if (this.y == t.y) {
                return this.x - t.x;
            }
            return this.y - t.y;
        }
    }

    public static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(win+"\n");
        if (win != 0) {
            bw.write(winSite[0]+" "+winSite[1]);
        }

        bw.flush();
        bw.close();
    }

    public static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        arr = new int[N+1][N+1];
        visit = new boolean[N+1][N+1][4];
        winSite = new int[2];

        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int j = 1; j <= N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        br.close();
    }
}

---

4. 결과 및 회고

이미 방문했던 위치에서 동일한 방향으로 뻗어나갔을 경우에는 다시 방문하지 않도록 visit 배열을 3차원 배열로 선언해주었다. 시간 초과 날까봐 3차원 배열로 선언했는데,, 근데 이렇게 안해도 시간초과 안날거같다. ㅎㅎ