[Python/파이썬] 백준 16929번: Tow Dots

문제

 

풀이

시작 지점과 같은 문자인 경우 dfs를 수행하고

길이가 4 이상이고 시작 지점으로 돌아온 경우 "Yes"를 출력하면 된다.

 

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [list(input().rstrip()) for _ in range(n)]
tempVisited = [[False] * m for _ in range(n)]

dir = ((0, 1), (0, -1), (1, 0), (-1, 0))

def dfs(c, sti, stj, nowi, nowj, cnt):
    for dx, dy in dir:
        ni, nj = nowi + dy, nowj + dx
        if (sti, stj) == (ni, nj) and graph[ni][nj] == c and cnt >= 4:
            print("Yes")
            exit()
        if ni < 0 or ni >= n or nj < 0 or nj >= m or tempVisited[ni][nj] or graph[ni][nj] != c:  continue
        tempVisited[ni][nj] = True
        dfs(c, sti, stj, ni, nj, cnt + 1)

for i in range(n):
    for j in range(m):
        tempVisited = [[False] * m for _ in range(n)]
        tempVisited[i][j] = True
        dfs(graph[i][j], i, j, i, j, 1)

print("No")

 

마무리

.