Python - [백준]2615-오목

문제

오목판이 주어지면 1번플레이어가 이겼는지 2번플레이어가 이겼는지 판단하는 문제이다. 육목인 경우는 제외하도록 한다.

접근 방법

오목은 8방향으로 다섯개를 연달아 놓으면 이기는 게임이다. 판에 0이 아닌부분을 차례대로 살펴보며 오목인지 판단한다. 모든 8방향을 볼 필요는 없고 중복을 방지하기위해 4방향을 살펴보면 된다.
맨 왼쪽 또는 맨 위에 돌 위치를 출력해야하므로 살펴보는 방향은

• 오른쪽 위, 오른쪽, 오른쪽 아래, 아래 4방향을 살펴본다.
• 6목의 가능성이 있으므로 방향 바로 전단계에 돌이 또 있는지도 검사한다.
• 승패가 갈리지않는다면 0을 출력한다.

풀이

dx, dy테크닉을 사용하여 살펴볼 방향을 설정한다. for문 두개를 배치하여 0이 아닌 모든 돌을 살펴본다. 그 후 큐를 사용하여 4방향에 대해 같은 돌이 있는경우 계속 큐에 넣으며 유효성을 검사한다.

• 큐의 길이가 5인경우
• 그 경우 바로 전단계 돌이 하나 더 있지 않은지 추가로 검사
• 만약 유효하다면 플레이어 번호와 큐 맨 앞의 원소를 출력

코드

from collections import deque 
arr = [list(map(int, input().split())) for _ in range(19)]
dx = [0, 1, 1, -1]
dy = [1, 1, 0, 1]

def is_range(x, y):
    return 0 <= x < 19 and 0 <= y < 19

for i in range(19):
    for j in range(19):
        queue = deque()
        if arr[i][j] != 0:
            for k in range(4):
                queue.append(arr[i][j])
                x, y = i, j
                while is_range(x+dx[k], y+dy[k]) and arr[x+dx[k]][y+dy[k]] == arr[i][j]:
                    queue.append(arr[x+dx[k]][y+dy[k]])
                    x += dx[k]
                    y += dy[k]
                if len(queue) == 5:
                    if not is_range(x-dx[k], y-dy[k]) and arr[i-dx[k]][j-dy[k]] == arr[i][j]:
                        break
                    else:
                        print(arr[i][j])
                        print(i+1, j+1)
                        exit()
                queue.clear()
print(0)