백준 2072 오목(구현)

https://www.acmicpc.net/problem/2072

2072번: 오목

처음엔 간단하게 돌을 놓은 순간 board 전체를 탐색해서 5칸이 이어진 구간이 있으면 그 순간의 i를 출력하는 간단한 문제로 생각했다.

 

하지만 이러한 경우 때문에 생각외로 잘 풀리지 않아 많은 시도를 한 후에 겨우 풀었다.

 

저런 조건때문에 탐색을 시작한 지점(x,y)에 대해 8방향까지 (x+5,y+5) 이렇게 탐색 하는 방법은 올바르지 않은 탐색이다.

 

(x,y)로 부터 8방향을 탐색하는데 (x,y)가 오목 5개의 중앙 지점이라고 생각하고 8방향에 대해 똑같은 돌이 몇개나 있는지 count를 세서 저장하는 것이다.

res = [0] * 8
std = board[x][y]
for k in range(8):
    nx = x + dx[k]
    ny = y + dy[k]
    while board[nx][ny]:
        if board[nx][ny] == std:
            nx += dx[k]
            ny += dy[k]
            res[k] += 1
        else:
            break

dx,dy의 index를 8방향에 대한 반시계방향 순서로 했기 때문에 index 4의 차이는 반대방향을 가르키게 된다.

for i in range(4):
    if res[i] + res[i+4] == 4:
        return True
return False

따라서 res[i] + res[i+4]의 값이 4이면 위의 6개 이상 돌이 놓여저 있는 경우를 제외하고 완벽하게 5개 있는 경우만 check

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

def check(x,y):
    res = [0] * 8
    std = board[x][y]
    for k in range(8):
        nx = x + dx[k]
        ny = y + dy[k]
        while board[nx][ny]:
            if board[nx][ny] == std:
                nx += dx[k]
                ny += dy[k]
                res[k] += 1
            else:
                break
    for i in range(4):
        if res[i] + res[i+4] == 4:
            return True
    return False

board = [[0] * 21 for _ in range(21)]

n = int(input())
for i in range(1,n+1):
    a,b = list(map(int,input().split()))
    if i % 2 == 1: #홀수(흑)
        board[a][b] = 1
    else: # 짝수(백)
        board[a][b] = 2

    if check(a,b) == True:
        print(i)
        exit()

print(-1)