[TIL] 백준 2615 - 오목 ( python )

📌 문제 탐색하기

N = 19

matrix = N * N 2차원 배열 바둑판

0 = 빈칸

1 = 흑돌

2 = 백돌

 

19×19 크기의 바둑판에서 각 칸에 0(빈칸), 1(흑돌), 2(백돌)이 놓여 있을 때, 오목이 있는지 판별하는 것이 핵심입니다. 단, 연속된 돌이 6개 이상이면 오목으로 인정하지 않습니다.

1 ≤ N ≤ 19

가능한 시간복잡도

• 보드의 크기는 19×19로 총 361칸입니다.
• 각 칸마다 최대 4가지 방향을 확인하며, 각 방향은 최대 19칸까지 연속 검사를 진행합니다.
  • 4가지 방향
    • 오른쪽: (y, x) = (0, 1)
    • 아래쪽: (y, x) = (1, 0)
    • 오른쪽 아래 대각선: (y, x) = (1, 1)
    • 오른쪽 위 대각선: (y, x) = (-1, 1)
• 최악의 경우 연산 횟수는 약 361 × 4 × 19 = 27,436회 정도로, 1초에 1천만 번 정도 처리하기에 시간 내에 충분히 처리 가능한 수준입니다. 

알고리즘 선택

모든 후보를 하나씩 검사하는 브루트포스 방법을 선택합니다.

현재 칸이 연속의 시작점인지 판단하기 위해, 반대쪽 칸을 먼저 체크합니다.
while 루프로 같은 돌이 연속되는지 세고, 정확히 5개인지 확인한 후, 5개가 넘으면 이긴 경우가 아닙니다.

 

---

📌 코드 설계하기

• 문제의 Input을 받습니다.
• 방향 배열을 설정합니다.
  • dy = [0, 1, 1, -1]
  • dx = [1, 0, 1, 1]
• 오목 보드판 탐색
  • 보드의 모든 칸을 순회합니다.
  • 돌이 있는 칸(0이 아닌 칸)에 대해 오목에서 이기는 지를 체크(check 함수)합니다.
  • 승리 조건에 맞는 돌을 찾으면 결과를 출력합니다.
• 체크 함수 작성
  • check(y, x) 함수를 만듭니다.
  • 현재 돌의 색을 stone 변수에 저장합니다.
  • 시작점 판단
    • prev_y = y - dy[i] 와 prev_x = x - dx[i]를 계산하여 범위 내에 같은 돌이 있는지 확인합니다.
    • 만약 있다면 이미 시작점에서 연속한 돌의 중간 부분으로 이 방향은 검사하지 않습니다.
  • 연속 돌 세기
    • 돌의 세는 변수인 count를 1로 초기화합니다.
    • 현재 좌표 이후의 칸부터 while 루프로 같은 돌이 계속 이어지는지 확인합니다.
    • while 루프를 돌면서 count를 증가시킵니다.
  • count 가 5개이면 해당 좌표와 돌의 색을 반환합니다.
  • 모든 방향을 검사한 후 count == 5인 조건을 만족하는 경우가 없다면 None을 반환합니다.
• 출력
  • 반환 결과에 따라 돌의 색과 좌표를 출력거나 0을 출력합니다.
  • 오목 보드판은 1부터 시작하기 때문에 반환된 좌표에 +1하여 출력합니다.

---

📌 정답 코드

import sys
input = sys.stdin.readline

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

dy = [0, 1, 1, -1]
dx = [1, 0, 1, 1]

def check(y, x):
    stone = matrix[y][x]

    for i in range(4):
        prev_y = y - dy[i]
        prev_x = x - dx[i]

        if 0 <= prev_y < N and 0 <= prev_x < N and matrix[prev_y][prev_x] == stone:
            continue

        ny = y + dy[i]
        nx = x + dx[i]

        count = 1
        while 0 <= ny < N and 0 <= nx < N and matrix[ny][nx] == stone:
            count += 1
            ny += dy[i]
            nx += dx[i]

        if count == 5:
            return(y, x, stone)

    return None

ans = None

for y in range(N):
    for x in range(N):
        if matrix[y][x] != 0:
            result = check(y, x)

            if result:
                ans = result
                break
    if ans:
        break

if ans:
    ans_y, ans_x, stone = ans
    print(stone)
    print(ans_y + 1, ans_x + 1)
else:
    print(0)