BOJ 2615 - 오목 링크
(2023.05.25 기준 S1)

문제

오목이 진행 중인 바둑판 상태가 주어진다.
정확하게 다섯 알이 연속으로 놓여야 이기는 상태라고 했을 때, 어떤 색이 이겼는지 출력

알고리즘

일일이 다 확인해야 한다.

풀이

진짜 별다른 테크닉이 필요가 없다. 모든 알마다 확인해주면 된다.
다만, 좀 어려울 수 있는 부분을 설명해보겠다.

이겼을 때, 연속된 다섯 개의 바둑알 중 가장 왼쪽에 있는 바둑알의 위치를 출력해야 한다.
이는, 행열 순서가 아니라 열행 순서로 탐색해주면 해결이 된다.

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

이런 TC가 들어온다면? "1 15 1"을 뱉는 코드 때문에 짜증날 수 있다.
이는 방문 체크를 6개 이상의 알이 놓였는지 확인할 때에 같이 방문 체크를 해버리면 해결이 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

int board[19][19], i, j, d, x, y;

// 0 - down, 1 - right, 2 - down_right, 3 - up_right
pii dir[4] = {{1, 0}, {0, 1}, {1, 1}, {-1, 1}};
bool visited[4][19][19];

bool check(){
    if (!(x < 19 && y < 19)) // 범위
        return false;
    if (board[x][y] != board[i][j]) // 돌 색깔
        return false;
    if (visited[d][x][y]) // 방문
        return false;
    visited[d][x][y] = true;
    return true;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    for (i = 0; i < 19; i++) for (j = 0; j < 19; j++) cin >> board[i][j];
    memset(visited, false, sizeof(visited));

    for (j = 0; j < 19; j++) for (i = 0; i < 19; i++){ // 왼쪽이 우선
        
        // 돌이 놓이지 않은 곳이면 패스
        if (!board[i][j]) continue;

        // 방향 차례대로 검사
        for (d = 0; d < 4; d++){
            x = i; y = j;
            auto [dx, dy] = dir[d];

            // 5개가 제대로 놓였는지 확인
            bool is_five = true;
            for (int _ = 0; _ < 5; _++){
                if (!check()){
                    is_five = false;
                    break;
                }
                x += dx; y += dy;
            }

            // 5개가 제대로 놓였다면 6개 이상이 놓이지 않았는지 확인
            if (is_five && !check()){
                cout << board[i][j] << '\n' << i + 1 << ' ' << j + 1;
                return 0;
            }
        }
    }

    cout << 0;
}

• Python

import sys; input = sys.stdin.readline

def check():
    if not (x < 19 and y < 19): # 범위
        return False
    if board[x][y] != board[i][j]: # 돌 색깔
        return False
    if visited[d][x][y]: # 방문
        return False
    visited[d][x][y] = True
    return True

board = [list(map(int, input().split())) for _ in range(19)]

# 0 - down, 1 - right, 2 - down_right, 3 - up_right
dir = [(1, 0), (0, 1), (1, 1), (-1, 1)]
visited = [[[False] * 19 for _ in range(19)] for _ in range(4)]

for j in range(19): # 왼쪽이 우선
    for i in range(19):

        # 돌이 놓이지 않은 곳이면 패스
        if not board[i][j]:
            continue

        # 방향 차례대로 검사
        for d in range(4):
            x, y = i, j
            dx, dy = dir[d]

            # 5개가 제대로 놓였는지 확인
            for _  in range(5):
                if not check():
                    break
                x += dx; y += dy
            else:
                # 6개 이상이 놓이지 않았는지 확인
                if not check():
                    print(board[i][j])
                    print(i + 1, j + 1)
                    exit()

print(0)