boj16929 two dots

🎯전형적인 DFS문제라는 생각이 들었음.
근데 순환 loop를 구하는 서울 지하철 2호선을 이미 풀었기 때문에 더 쉽게 할 수 있었던 것 같다. 다만! 이 문제는 matrix 구조라서 그에 맞게 문제만 변형해주면 되었음!

처음에 에러가 떴었는데 어디서 떴냐면..

# 이렇게 하면 한번 탐색하고 이전 것 방문 표시 되어서 바로 True 반환함.
        elif 0<=nx<n and 0<=ny<m and card[nx][ny] == color and \
        visit[nx][ny] is True and cnt >= 2:

바로 이 부분이다.. 다음 노드 탐색할 때 바로 이전 노드가 조건에 걸려버림...
그래서 생각을 하다가 그냥 각 노드에 대해서 순환인지 파악했던 서울 지하철 2호선 문제처럼 풀어야 되겠구나 이 생각이 듦.

📍start node is next node 라면 순환선 이라는 로직을 이용했음

뭔가 brute force 느낌으로 풀어버려서 사실 런타임 에러 뜰 줄 알았는데 안 뜨더라고... 보니까 data 갯수가 엄청 적었음. 흠... 일단 나중에 좀 더 좋은 알고리즘 생각해 봐야겟다.. 피곤해서 자러 가야함 ㅠㅠ

import sys
sys.stdin = open('test.txt', 'r')

n, m = map(int, input().split())
# print 찍어보면 개행 들어있어서 rstrip 이용
card = [list(sys.stdin.readline().rstrip()) for _ in range(n)]
flag = False

def dfs(start, next, color, visit, cnt):
    global flag
    a, b = next
    visit[a][b] = True
    for i in range(4):
        nx = a + dx[i]
        ny = b + dy[i]
        # 범위 안이고 같은 컬러이면서 방문하지 않았을 때
        if 0<=nx<n and 0<=ny<m and card[nx][ny] == color and visit[nx][ny] is False:
            dfs(start, (nx,ny), color, visit, cnt + 1)
        # 범위 안이고 같은 컬러이면서 방문했다면 순환구조

        # 이렇게 하면 한번 탐색하고 이전 것 방문 표시 되어서 바로 True 반환함.
        elif start == (nx, ny) and 0<=nx<n and 0<=ny<m and card[nx][ny] == color and visit[nx][ny] is True and cnt >= 2:
            flag = True
            return



dx=[1,-1,0,0]
dy=[0,0,1,-1]
for i in range(n):
    for j in range(m):
        visit = [[False] * m for _ in range(n)]
        dfs((i,j),(i,j), card[i][j], visit, 0)

if flag is True:
    print("Yes")
else:
    print("No")