[백준] 16929번(Two Dots)

백준 16929번

최종 제출 코드

import sys
from collections import deque

input = sys.stdin.readline

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

n, m = map(int, input().split())
array = []
visited = [[0 for _ in range(m)] for _ in range(n)]

for i in range(n):
  array.append(list(input()))

queue = deque()

def bfs():

  while queue:
  
    x, y = queue.popleft()
    cnt = 0
    
    for i in range(4):
      # 접근하려는 좌표가 인덱스 범위를 벗어난다면 접근할 수 없음
      if x + dx[i] < 0 or x + dx[i] >= m or y + dy[i] < 0 or y + dy[i] >= n:
        continue
        
      # 접근하려는 인덱스의 원소가 현재 좌표의 원소와 같지 않다면 접근할 필요 없음
      if array[y + dy[i]][x + dx[i]] != array[y][x]:
        continue
        
      # 접근하려는 인덱스의 visited 값이 0이라면 해당 값을 업데이트하고 queue에 append
      if visited[y + dy[i]][x + dx[i]] == 0:
        visited[y + dy[i]][x + dx[i]] = visited[y][x] + 1
        queue.append([x + dx[i], y + dy[i]])

	  # 현재 인덱스가 start node가 아니며, 인접한 두 개의 노드에서 같은 visited 값을 가진다면 이 그래프는 순환임
      if visited[y][x] !=1 and visited[y + dy[i]][x + dx[i]] == visited[y][x]-1:
        cnt += 1

	# 인접한 노드에서 같은 값이 발견되면 True를 return
    if cnt > 1:
      return True

  return False

chk = False

# [0,0]부터 방문한 적 없는 노드에 대해 bfs 실행
for i in range(n):
  if chk:break
  for j in range(m):
    if visited[i][j] == 0:
      visited[i][j] = 1
      queue.append([j, i])
      chk = bfs()
      if chk==True:break

print("Yes") if chk else print("No")

◼️ 순환되는 그래프를 bfs로 탐색한다면

• 경로의 분기가 시작되는 노드와 다시 만나는 노드가 있어야 한다.
• 탐색하는 노드들이 사각형의 형태를 띄고 있기 때문에, 분기가 시작되는 노드부터 다시 만나는 노드까지의 경로들의 거리는 동일하다.
• 따라서 현재 탐색중인 노드와 인접한 노드들의 visited 값을 검사하여, 현재 노드의 visited값 - 1과 일치하는 인접 노드가 2개 존재한다면 이 그래프는 순환하는 그래프이다.