[99클럽 코테 스터디 TIL 14일차 / 백준 2615] 오목 (Python)

후우우 BFS로 풀까 하다가 저번 문제로 DFS를 오랜만에 쓰게 돼서 DFS에도 익숙해지고자 이 문제는 DFS로 풀기로 하였다

 

그냥 BFS로 풀 걸 ... 후우

이 문제 푸는데 4시간 반이 걸렸다 .. ^,^

 

내 코드

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

color = 0
answer = (-1, -1)
direct = [(0, 1), (1, 1), (1, 0), (-1, 1)]
def DFS(loc, dir, loc_l):
    global color, answer
    # 5목일 때
    if len(loc_l) == 5:
        a = loc_l[0][0] - direct[dir][0]
        b = loc_l[0][1] - direct[dir][1]
        A = loc[0] + direct[dir][0]
        B = loc[1] + direct[dir][1]
        # 6목일 때
        if 0 <= a < 19 and 0 <= b  < 19 and graph[a][b] == graph[loc[0]][loc[1]]:
            pass
        elif 0 <= A < 19 and 0 <= B < 19 and graph[A][B] == graph[loc[0]][loc[1]]:
            pass
        # 6목 아닐 때
        else:
            print(graph[loc[0]][loc[1]])
            print(loc_l[0][0] + 1, loc_l[0][1] + 1)
            sys.exit(0)
        
    for d in range(4):
        x = loc[0] + direct[d][0]
        y = loc[1] + direct[d][1]
        # 바둑돌 색깔이 같을 때
        if x >= 0 and x < 19 and y >= 0 and y < 19 and graph[loc[0]][loc[1]] == graph[x][y]:
            # 첫 바둑돌과 연속이거나 새로운 방향으로 연속인 바둑돌일 때
            if dir == -1 or dir != d:
                DFS((x, y), d, [loc, (x, y)])
            # 같은 방향으로 연속인 바둑돌일 때
            else:
                loc_l.append((x, y))
                DFS((x, y), dir, loc_l)
                loc_l.pop()

def main():
    for i in range(19):
        for j in range(19):
            if graph[i][j] > 0:
                DFS((i, j), -1, [(i, j)])
    print(0)

main()

일단 탐색 방향은 오른쪽, 오른쪽 아래 대각선, 아래, 오른쪽 위 대각선 총 네가지로 설정하였다.

이렇게 방향을 설정한 이유는 모두 처음으로 탐색한 위치가 맨 왼쪽이기 때문이다.

 

1. DFS함수의 인자는 loc(위치), dir(방향), loc_l(연속된 바둑돌들의 위치 리스트) 이다.

2. 인자로 받은 위치에서 4가지 탐색 방향에 위치한 바둑돌을 확인한다.

3. 탐색한 돌이 현재 돌과 같은 색일 때, 첫 바둑돌과 연속인 경우와 이전과 다르게 새로운 방향으로 연속일 경우에 인자가 탐색 돌 위치, 새로운 방향, [현재 돌 위치, 탐색 돌 위치] 리스트인 DFS 재귀함수를 호출한다.

4. 3번과 다르게 계속 같은 방향으로 연속인 돌인 경우, 탐색 돌 위치, 방향, 탐색 돌 위치가 추가된 loc_l 을 인자로 갖는 DFS 재귀함수 호출한다.

5. 5목인 경우에 시작 지점의 전 방향 또는 끝 지점의 후 방향에 같은 색일 경우 6목이기 때문에 pass 해준다.

6. 6목이 아닌 경우, 5목에 해당하므로 돌의 색과 처음 시작한 돌의 위치를 출력해준다.

7. 모든 경우에도 시스템 종료가 안된 것은 이긴 돌이 없는 것이기 때문에 0을 출력해준다.

 

실패 요인

1. 6목을 체크해주지 않는 것

2. 처음에 탐색방향을 오른쪽 위 대각선이 아닌, 왼쪽 아래 대각선으로 해주었다

- 이렇게 설정해줄 경우 왼쪽으로 되돌아 오는 경우가 생기는데 이때 새로운 방향이므로 6목 이상인데도 새로운 지점에서 시작한다고 판단해 5목으로 출력해버린다.

3. visited 방문 체크