[python] 백준 16929 Two Dots

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

16929번: Two Dots

 

 

문제 해결

• DFS를 이용하기 좋다고 생각되는 문제
• Cycle을 만들면 되므로 시작점에서 출발하여 방문하지 않은 길로 가서 다시 시작점으로 돌아올 수 있으면 cycle이 만들어지므로 바로 print("Yes") 출력하고 exit()를 통해 코드 종료
• 시작점을 (0,0) 부터 (n-1,m-1) 까지 m*n 개를 모두 돌리는 것이 마음에 안들지만 다른 방법이 생각이 안난다...ㅜㅜ
• 시작점을 기준으로 방문했던 점은 기록해야하므로 visited 리스트롤 통해 기록을 하고 그 경우 cycle이 안만들어지면 그대로 visited = False를 통해 기록을 지워준다.
• cycle을 만들려면 최소 시작점 포함 4개의 점을 지나야하므로 cnt를 통해 지나간 점의 수를 count 한다.

CODE

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

board = [list(str(input().rstrip())) for _ in range(n)]

move = [(-1,0), (1,0), (0,1),(0,-1)]
visited = [[False for _ in range(m)] for _ in range(n)]
ans = 0
def solve(alpha, row, col, cnt):
    global ans
    if ans:
        print("Yes")
        exit()
    for i in range(len(move)):
        new_row, new_col = row+move[i][0], col+move[i][1]
        if new_row<0 or new_row>=n or new_col <0 or new_col>=m:
            continue
        elif cnt >=4 and new_row == start_row and new_col == start_col:
            ans =1
            print("Yes")
            exit()
        if board[new_row][new_col] == alpha and visited[new_row][new_col]==False:
            visited[new_row][new_col] = True
            solve(alpha, new_row, new_col, cnt+1)
            visited[new_row][new_col] = False

for row in range(n):
    for col in range(m):
        visited[row][col] = True
        start_row, start_col = row, col
        solve(board[row][col],row,col,1)
        visited[row][col] = False
print("No")