[알고리즘] 백준 16929 'Two Dots' 풀이 _ 파이썬

백준 16929 Two Dots
https://www.acmicpc.net/problem/16929
난이도 : 골드 4
유형 : DFS

풀이

최근 코딩테스트에 그래프 문제가 많이 나오고 있다고 해서 그래프 문제들을 다시 공부해보고 있다.

이 문제는 2차원 배열에서 색깔이 같은 칸들을 따라갔을 때, 사이클이 존재하는 지 여부를 판단하는 문제다.

나는 사실 Two Dots라는 게임을 알고 있어서 당연히 게임 규칙처럼 네모 사각형 사이클을 만들어야하는 줄 알고 시간을 많이 소요했는데 모양과 관계없이 사이클을 만들기만 하는 문제였음...

어떤 모양으로든 사이클이 만들어지기만 하면 되기 때문에 DFS로 같은 색깔의 칸들을 따라가다가 이미 방문한 칸을 마주쳤을 때 사이클이 존재한다고 판단하기로 했다.

이 때, 진행하던 방향의 역방향, 즉 U턴을 하게 되면 방문한 칸이지만 사이클이 만들어지지 않기 때문에 이 부분은 조건으로 제외해줬다.

정답 코드

import sys
input = sys.stdin.readline
from collections import deque

N, M = map(int, input().split())

matrix = []
for _ in range(N):
    line = list(map(str, input().strip('/n')))
    matrix.append(line)

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

start = ''

visited = [[0] * M for _ in range(N)]

answer = "No"

#방향을 알기위한 d
def dfs(x, y, d):
    global answer, visited
    for i in range(4):
    	#역방향으로 진행하는 부분을 제외해주기 위한 코드
        #dx, dy를 만들 때 인덱스 0, 2이 세로 방향, 1, 3을 가로방향으로 정했기 때문에
        #방향이 서로 같지 않으면서 홀짝이 같을 때를 제외해줬다
        if d != -1 and d != i and d % 2 == i % 2:
            continue
        nx = x + dx[i]
        ny = y + dy[i]

	#칸 색이 같을 때 진행
        if 0 <= nx < N and 0 <= ny < M and matrix[nx][ny] == start:
            #이미 방문한 경우 사이클이 존재
            if visited[nx][ny] == 1:
                answer = "Yes"
                return
            visited[nx][ny] = 1
            dfs(nx, ny, i)

for i in range(N):
    for j in range(M):
        if visited[i][j] == 0:
            start = matrix[i][j]
            dfs(i, j, -1)
            if answer == "Yes":
                print(answer)
                sys.exit()

print(answer)

로직 자체는 복잡하지 않았다.
DFS를 진행하면서 방향을 같이 넘겨주고, 그 방향의 역방향으로는 가지 않는 게 핵심