[문제 풀이 13] 코드 트리 - 오목의 승패

오목의 승패

 

• 문제 유형 : Simulation, BFS
• 사용언어 : Python
• 난이도 : 실버 3
• 출처 : 코드 트리

 

https://www.codetree.ai/training-field/my-lists/20228/concave-victory-and-defeat/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

def bfs(x, y):
    target = graph[x][y]

    for dx, dy in direction:
        cnt = 1
        nx = x + dx
        ny = y + dy

        while 0 <= nx < 19 and 0 <= ny < 19 and graph[nx][ny] == target:
            cnt += 1

            if cnt == 5:
 
                if 0 <= x - dx < 19 and 0 <= y - dy < 19 and graph[x - dx][y - dy] == target:
                    break
                if 0 <= nx + dx < 19 and 0 <= ny + dy < 19 and graph[nx + dx][ny + dy] == target:
                    break

                print(target)
                print(x + 1, y + 1)
                exit(0)

            nx += dx
            ny += dy


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

direction = [(0, 1), (1, 0), (1, 1), (-1, 1)]

for i in range(19):
    for j in range(19):
        if graph[i][j] != 0:
            bfs(i, j)

print(0)