[Algorithm] 99클럽 코테 스터디 14일차 TIL BOJ 2615

문제

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

풀이

문제 분석

• 처음에는 탐색 위치로부터 8방향을 탐색하여 5개의 바둑돌을 만족하는 시점에서 탐색을 멈추도록 로직을 구현했다
• 그러나 이 방식을 사용하면 문제에서 요구하는 왼쪽 상단의 시작점을 알기 어렵다는 한계가 존재했다
• 따라서 탐색은 항상 왼쪽부터 진행하도록 하고 진행 방향은 다음과 같이 4가지로만 제한하여 시작점이 항상 왼쪽 혹은 맨 위에 존재하도록 하였다!
  

• 또한 6, 7목을 고려하지 못하는 경우도 존재했는데, 이는 다음과 같은 상황이 발생할 수 있으므로 오목이라고 판단한 후에 시작점의 이전 칸도 함께 검사를 꼭 해주어야 했다
  

코드

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

public class Main {
    private static int[][] board;
    private static boolean[][] visited;
    static int[] dx = {-1, 0, 1, 1};
    static int[] dy = {1, 1, 1, 0};
    static int count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        board = new int[20][20];
        visited = new boolean[20][20];

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

        for (int i = 1; i <= 19; i++) {
            for (int j = 1; j <= 19; j++) {
                int currentColor = board[i][j];
                visited = new boolean[20][20];

                if (currentColor != 0) {
                    for (int dir = 0; dir < 4; dir++) {
                        int x = i + dx[dir];
                        int y = j + dy[dir];
                        count = 1;
                        if (isValid(x, y) && board[x][y] == currentColor) {
                            visited[x][y] = true;
                            count++;
                            dfs(x, y, dir, currentColor);
                        }
                        if (count == 5 && checkFive(i, j, dir, currentColor)) {
                            bw.write(currentColor + "\n");
                            bw.write(i + " " +j);
                            bw.flush();
                            bw.close();
                            return;
                        }
                    }
                }
            }
        }

        bw.write('0');
        bw.flush();
        bw.close();
    }

    private static void dfs(int x, int y, int dir, int color) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if (isValid(nx, ny) && !visited[nx][ny] && board[nx][ny] == color) {
            count++;
            visited[nx][ny] = true;
            dfs(nx, ny, dir, color);
            visited[nx][ny] = false;
        }
    }

    private static boolean isValid(int x, int y) {
        return x >= 1 && x <= 19 && y >= 1 && y <= 19;
    }

    private static boolean checkFive(int x, int y, int dir, int color) {
        int beforeX = x - dx[dir];
        int beforeY = y - dy[dir];

        if (beforeX < 1 || beforeY < 1 || beforeX > 19 || beforeY > 19) {
            return true;
        }
        return board[beforeX][beforeY] != color;
    }
}

TIL

• 완전탐색을 효율적으로 하기 위한 규칙을 생각하는게 중요한 문제였던 것 같다
• 또한 dx, dy와 i, j와의 상관관계를 설정하는 부분에서 평소와 다르게 헷갈렸다..
• x를 가로, y를 세로라고 생각하는 순간부터 엄청나게 헷갈리기 시작하니 i와 j가 각각 행과 열이라는 점을 인지하고 헷갈리지 않게 문제를 풀어야 할 것 같다