[알고리즘/백준] 2072번 오목 Python 파이썬

 

한동안 문제가 어려워서 직접 풀지 못하고 풀이를 참고한 경우가 많아서 글을 못 올렸네요... 오래만에 스스로 풀 수 있는 문제가 나와서 좋았습니다. 이번 문제는 문제로 많이 등장하는 오목 문제입니다.

 

 

문제가 길어서 중간에 생략하고 시작과 끝만 첨부합니다. 문제를 요약하면 돌 좌표가 흑, 백 번갈아가면서 놓여질 때 오목이 되는지 안되는지 확인해서 만약에 오목이 된다면 해당 돌 번째를 출력하는 문제입니다.

주의할 부분은 승패가 갈리지 않은 경우 -1를 해주고 놓았을 때 오목(=5)이 아닌 6 등 그 이상이 된다면 오목으로 안치고 그대로 게임을 이어간다는 점입니다.

 

저 같은 경우 문제를 보고 dfs 로 풀어야겠다고 생각하고 풀었습니다. 다만 다 풀고 나서 생각해보니 dfs보다는 bfs 방식이 좀 더 코드 줄을 줄이고 효율적일 수 있다고 생각이 들었습니다. 

 

아래와 같은 코드로 통과하였습니다.

 

import sys
input = sys.stdin.readline

n = int(input())
answer = 0
map_list = [[-1]*19 for i in range(19)]
map_visited = [[False]*19 for i in range(19)]

def check_bingo():
    c = 0
    for k in range(19):
        for u in range(19):
            if map_visited[k][u] == True:
                c += 1
    if c == 5:
        return True
    else:
        return False

def reset_visited():
     for k in range(19):
        for u in range(19):
            map_visited[k][u] = False

def check_dfs(x, y, wh):
    for g in range(4):
        reset_visited()
        dfs(x,y,wh, g)
        if check_bingo() == True:
            return True
    return False

def dfs(x, y, wh, n):
    if 0 <= x < 19 and 0 <= y < 19 and map_visited[x][y] == False and map_list[x][y] == wh:
        map_visited[x][y] = True
        
        if n == 0:
            dfs(x+1, y, wh, n)
            dfs(x-1, y, wh, n)
        elif n == 1:
            dfs(x, y+1, wh, n)
            dfs(x, y-1, wh, n)
        elif n == 2:
            dfs(x+1, y+1, wh, n)
            dfs(x-1, y-1, wh, n)
        elif n == 3:
            dfs(x+1, y-1, wh, n)
            dfs(x-1, y+1, wh, n)

for i in range(n):
    x, y = map(int, input().split())
    if i%2 == 0:
        map_list[x-1][y-1] = 0
    else:
        map_list[x-1][y-1] = 1
    if check_dfs(x-1, y-1, map_list[x-1][y-1]) == True:
        print(answer+1)
        exit()
    else:
        answer += 1 
print(-1)

 

사실 참고하기에는 비효율적인 코드라고 생각합니다. dfs 를 통해 구현하다보니 오목했는지 확인하는 과정을 일일이 전체 판을 돌면서 지나간 곳을 카운트해주는 방식을 사용했는데 bfs 방식을 사용했다면 바로바로 카운트해서 확인할 수 있었다고 생각합니다.

 

고로 해당 문제를 풀기 위해 글을 보신 분은 bfs 를 통해서 풀거나 bfs 풀이 방식을 찾아보는 것을 추천드립니다. 위 코드는 bfs 외 다른 풀이 코드나 dfs 를 통해서 풀고 싶을 때 참고하면 좋을 거 같습니다.