문제 : https://www.acmicpc.net/problem/16929

접근

DFS 또는 BFS를 통해 풀 수 있다. (여기서는 DFS 사용)

일반 DFS와 다른 점은 한 바퀴를 도는 cycle을 만들어야 한다는 것이다.
visited 리스트를 만들어 True, False를 체크하는 것 만으로는 사이클 여부를 알 수 없다.

주요 아이디어

(노란색 셀에 주목)

• 사이클을 따라 순서대로 번호를 매길 때, 사이클이 완성되는 지점에서(노란색 숫자) 두 Dots의 차이는 최소 3 이상이다.

풀이

그래프의 모든 점에 대해 DFS를 진행한다.

1. DFS를 돌 때, 다음 자신이 방문할 지점에 자신의 값 + 1를 저장함으로써 순서를 매긴다.

2. 다음 자신이 방문할 지점이 이미 방문한 노드이면 자신의 값 - 방문할 노드의 값을 구한다.

   • 3이상일 경우 : 사이클이 완성되는 지점이란 뜻으로 'Yes'를 반환하고 프로그램 종료

   • 2이하일 경우 : 사이클이 아니므로 무시하고 다음 노드를 찾는다.

모든 점에 대해 DFS를 진행했는데도 사이클을 찾지 못했다면 'No'를 반환하고 프로그램 종료

코드

import sys

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

def DFS(x, y):
    for i in range(4):
        xx = x+dx[i]
        yy = y+dy[i]
        if 0<=xx<N and 0<=yy<M and board[xx][yy] == board[x][y]:
            if visited[xx*M+yy]:
                if visited[x*M+y] - visited[xx*M+yy] >= 3:
                    print('Yes')
                    sys.exit(0)
                continue
            visited[xx*M+yy] = visited[x*M+y] + 1
            DFS(xx, yy)
            visited[xx*M+yy] = 0

N, M = map(int,input().split())
board = [list(map(str, input().rstrip())) for _ in range(N)]

# 1차원 배열로 2차원 그래프를 해결하는 연습을 하고 싶어서 1차원으로 선언
visited = [0] * (N*M)

for i in range(N):
    for j in range(M):
        visited[i*M+j] = 1
        DFS(i, j)
        visited[i*M+j] = 0

print('No')

코멘트

• 지금까지 DFS나 BFS에서 이미 방문한 노드는 별다른 처리 없이 무조건 스킵만 했었는데
  방문한 노드를 활용해서 원하는 결과를 얻을 수 있다는 것을 알았다.
  앞으로 DFS, BFS를 풀 때 재방문 시 처리를 통해 결과를 도출할 수 있는지도 확인해야겠다.

• 2차원 리스트를 1차원 리스트로 처리하는 방법을 연습해 봤는데, 다행히 꼬이지 않고 잘 되었다.

• 다음부터는 백준 문제풀이를 슈도코드처럼 적는 연습을 해야겠다.