Programming/Python

[파이썬] 백준 16929번: Two Dots

IN.0 2020. 5. 1. 02:43
728x90
반응형
dx = [-1, 1, 0, 0]	# 상하좌우
dy = [0, 0, -1, 1]
def DFS(x, y):
    global answer
    visited[x][y] = 1	# 방문 체크
    for d in range(4):
        X = x + dx[d]
        Y = y + dy[d]
        if 0 <= X < N and 0 <= Y < M:	# 다음 타겟이 board 안에 있으면
            if board[X][Y] == board[x][y]:		# 값(색깔)이 같으면
                if visited[X][Y] == 0:	# 아직 방문한 적이 없다면
                    my_snake.append([X, Y])		#방문 순서에 기록한다
                    DFS(X, Y)	# 방문하러 가기 (재귀)
                    my_snake.pop()	# 방문 순서에서 제외한다
                else:		# 방문한 적이 있다면
                    if X == my_snake[-2][0] and Y == my_snake[-2][1]:	# 바로 전에 방문한 곳이면
                        pass
                    else:	# 바로 전은 아닌데 언젠가 방문한 적이 있음 (사이클 형성)
                        answer = 'Yes'	# 답을 바꾸고 바로 빠져나간다
                        return
        if answer == 'Yes':
            return

N, M = map(int, input().split())
board = []
visited = [[0]*M for _ in range(N)]	# 방문 체크용
for _ in range(N):
    board.append(input())

answer = 'No'	# 기본값은 No
for i in range(N):
    for j in range(M):
        if visited[i][j] == 0:	# 해당 구역을 방문한 적이 없다면
            my_snake = [[i, j]]	# 방문 순서 기록용
            DFS(i, j)
        if answer == 'Yes':	# 답이 바뀌면 바로 빠져나온다.
            break
    if answer == 'Yes':
        break

print(answer)
728x90
반응형