[BOJ] 16929 Two Dots - Python

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

16929번: Two Dots

 

bfs + 구현 문제이다.

사이클을 어떻게 처리할 지에 대한 생각이 조금 필요했던 문제이다.

나는 visit의 카운트로 처리를 했다.

다른 사람들은 어떻게 처리를 했는지 보러가야지..

from collections import deque
dx = [-1,1,0,0]
dy = [0,0,-1,1]
N, M = map(int, input().split())
arr = [[0]*M for _ in range(N)]
visit = [[0]*M for _ in range(N)]
# alpha = [0]*27
for i in range(N):
    li = input()
    for j in range(M):
        arr[i][j] = li[j]
# 체크가 True면 "Yes"
check = False
# 2차원 배열 다 돌면서
for i in range(N):
    for j in range(M):
    	#visit가 False인거만
        if visit[i][j] == False:
            visit[i][j] = 1
			# bfs돌리기 위한 q
            q = deque()
            # x좌표, y좌표, 거리, 알파벳을 q에 넣어준다.
            q.append((i, j, 0, arr[i][j]))
            while q:
                x,y,cnt,alpha = q.popleft()
                for k in range(4): #4방향을 돌면서
                    xx = x + dx[k]
                    yy = y + dy[k]
                    if 0<=xx<N and 0<=yy<M: #좌표가 벗어나지 않을 때
                    	# 카운트가 1 이상, 다음에 방문할 좌표의 visit이 전의 좌표visit +1 이고 알파벳이 같으면 사이클.
                        if cnt >= 1 and visit[xx][yy] == visit[x][y]+1 and alpha == arr[xx][yy]:
                            check = True
                            break
                        # 뒤로가지 않게
                        if cnt == 1 and arr[xx][yy] == 0:
                            continue
                        # bfs 도는 부분
                        if visit[xx][yy] == False and alpha == arr[xx][yy]:
                            q.append((xx,yy,cnt+1,alpha))
                            visit[xx][yy] += visit[x][y] + 1
                if check:
                    break
        if check:
            break
    if check:
        break
if check:
    print("Yes")
else:
    print("No")