[Python/Java] 백준 2615 - 오목 [Brute Force]

문제

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

 

해설

반복문을 이용한 완전 탐색 방법으로 해결할 수 있었다. DFS로도 접근해보았는데 잘 해결되지 않아 방법을 바꾸어 다시 접근하였다.

 

6목이 되는 케이스에 대한 검사가 필요했고, directions 부분에 왔던 방향을 되돌아가지 않도록 설정하는 아이디어도 주요했던 것 같다.

 

Python

from sys import stdin


# 방향: 오른쪽, 아래, 대각선(↘), 대각선(↗)
directions = [(0, 1), (1, 0), (1, 1), (-1, 1)]


def check_winner(row: int, col: int, direction: tuple):
    stone = board[row][col]
    depth = 1

    x, y = row, col
    for _ in range(4):
        x += direction[0]
        y += direction[1]
        if 0 <= x < 19 and 0 <= y < 19 and board[x][y] == stone:
            depth += 1
        else:
            break

    # 정방향(positive direction) 확인
    px, py = x + direction[0], y + direction[1]
    if 0 <= px < 19 and 0 <= py < 19:
        if board[px][py] == stone:
            return False

    # 역방향(negative direction) 확인
    nx, ny = row - direction[0], col - direction[1]
    if 0 <= nx < 19 and 0 <= ny < 19:
        if board[nx][ny] == stone:
            return False

    if depth == 5:
        return True
    return False


board = [list(map(int, stdin.readline().strip().split(" "))) for _ in range(19)]

win = False
for i in range(19):
    for j in range(19):
        if board[i][j] != 0:
            for direction in directions:
                win = check_winner(i, j, direction)
                if win:
                    print(board[i][j])
                    print(i+1, j+1)
                    exit(0)
if not win:
    print(0)

 

Java

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

public class Main {
    static int[][] board = new int[19][19];
    static int[][] directions = {{0, 1}, {1, 0}, {1, 1}, {-1, 1}}; // →, ↓, ↘, ↗

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        for(int i = 0; i < 19; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < 19; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i = 0; i < 19; i++) {
            for(int j = 0; j < 19; j++) {
                if(board[i][j] != 0) {
                    for(int[] direction : directions) {
                        if(checkWinner(i, j, direction)) {
                            System.out.println(board[i][j]);
                            System.out.println((i + 1) + " " + (j + 1));
                            return;
                        }
                    }
                }
            }
        }
        
        System.out.println(0);
    }

    public static boolean checkWinner(int row, int col, int[] direction) {
        int stone = board[row][col];
        int count = 1;

        int x = row, y = col;
        for(int i = 0; i < 4; i++) { // 4칸 더 확인
            x += direction[0];
            y += direction[1];
            if (x >= 0 && x < 19 && y >= 0 && y < 19 && board[x][y] == stone) {
                count++;
            } else {
                break;
            }
        }

        // 정방향(positive direction) 확인
        int px = x + direction[0], py = y + direction[1];
        if(px >= 0 && px < 19 && py >= 0 && py < 19 && board[px][py] == stone) {
            return false;
        }

        // 역방향(negative direction) 확인
        int nx = row - direction[0], ny = col - direction[1];
        if(nx >= 0 && nx < 19 && ny >= 0 && ny < 19 && board[nx][ny] == stone) {
            return false;
        }

        return count == 5;
    }
}