문제
19×19 바둑판에 흑백이 번갈아 돌을 놓는다. 정확히 5개가 연속으로 놓이는 순간의 수 번째를 출력하라. 오목이 만들어지지 않으면 -1을 출력한다.
입력
첫째 줄에 수 N, 이후 N줄에 놓는 좌표가 주어진다 (홀수 번째가 흑).
출력
오목이 처음 완성되는 수 번째를 출력한다. 없으면 -1.
예제
| 입력 | 출력 |
|---|---|
5 1 1 2 2 1 2 2 3 1 3 | -1 |
풀이
매 수마다 놓은 돌을 기준으로 8방향 탐색을 하여 정확히 5연속인지 확인한다.
- 각 돌을 놓은 후, 8방향(4쌍)으로 같은 색 돌의 연속 개수를 센다
- 양방향 쌍의 합에서 자기 자신 중복을 빼면 한 줄의 연속 개수가 된다
- 정확히 5개이면 해당 수 번째를 출력하고 종료한다
- 모든 수를 처리해도 오목이 없으면 -1을 출력한다
핵심 아이디어: 마지막에 놓은 돌을 포함하는 줄만 확인하면 되므로, 매번 4개 방향 쌍만 검사하면 충분하다.
코드
import sys
n = int(sys.stdin.readline())
l = [()] + [tuple(map(int, sys.stdin.readline().split())) for i in range(n)]
answer = -1
board = [[-1] * 19 for i in range(19)]
direction = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
found = False
for i in range(1, n + 1):
x, y = l[i][0] - 1, l[i][1] - 1
board[x][y] = i % 2
count = [0] * 8
for j in range(8):
dx, dy = direction[j]
tc = 0
nx, ny = x, y
while 0 <= nx < 19 and 0 <= ny < 19:
if board[nx][ny] != i % 2:
break
tc += 1
nx, ny = nx + dx, ny + dy
count[j] = tc
for j in range(4):
c = count[j] + count[j + 4] - 1
if c == 5:
answer = i
found = True
break
if found:
break
print(answer)복잡도
- 시간: O(N * 19) — 매 수마다 최대 4방향 × 19칸 탐색
- 공간: O(19²) — 바둑판 배열