16929번 - Two Dots

사이클을 돌리는 문제입니다.
그래프가 주어졌을 때, 위에 보시는 사진과 같이 시작점에서 다른 점과 겹치지 않게 다시 돌아와 사이클을 형성 할 수 있으면 Yes, 그게 아니라면 No를 출력하면 되는 탐색 문제입니다.

초기 구상

일단 문제를 보고 떠오른 건 시작점에서부터 visited로 표기하면서 DFS로 탐색을 이어나가되 탐색의 횟수가 3회 이상이 되면서 현재 위치에서 4방향 탐색을 했는데 시작점이 나온다면 사이클(직사각형)이 형성 될 수 있으므로 Yes를 출력하면 된다...는 느낌으로 생각을 정리했습니다.

기본 변수 선언

N,M = map(int,input().split())
graph = []
distance = 0
boolean = False
ans = []
visited = [[0]*M for _ in range(N)]
for _ in range(N):
    graph.append(list(input()))

그래프와 방문여부, 탐색 거리 및 bool 값을 선언해주겠습니다.

for i in range(N):
    for j in range(M):
        dfs(i,j,i,j)
        visited = [[0]*M for _ in range(N)]
        distance = 0

각 인덱스마다 탐색을 돌아 나오는 결과가 다 틀리므로 모든 인덱스에서 DFS 탐색을 다 돌겠습니다.

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline 

dx = [-1,1,0,0]
dy = [0,0,1,-1]

파이썬에서 DFS 탐색을 수행하기 위해 기본적으로 하는 것들입니다.
recursionerror에 걸리지 않기 위해 setrecursionlimit, 시간초과를 피하기 위한 sysinput등을 가져오고 상하좌우 DFS 탐색을 수행하기 위해서 dx와 dy등을 선언하겠습니다.

DFS 수행

def dfs(x,y,first_x,first_y):
    global distance,boolean
    visited[x][y] = 1

먼저 방문처리를 해줍니다. first_x,first_y는 시작점 표기로 뭐 딱히 연산하는데 써먹을 게 아닌 시작점으로 돌아갈 수 있는지 확인해주기 위해서 끌고 온 변수입니다.

    for i in range(4):
        nx = dx[i] + x
        ny = dy[i] + y

4방향 탐색을 실시해주고

        if [nx,ny] == [first_x,first_y] and distance > 2:
            boolean = True

만약 거릿값이 3 이상이고 현재 조사중인 인덱스에서 시작점으로 돌아가는게 가능하다! 하면 boolean 값을 True로 리턴해줍시다.

        if nx<0 or ny<0 or nx>=N or ny>=M:
            continue

그래프 밖을 벗어나서 탐색하려 시도한다면 continue로 해당 탐색위치는 넘겨버리고

        if not visited[nx][ny] and graph[nx][ny] == graph[x][y]:
            distance += 1
            # print(boolean,'x 탐색구간:',nx,'y 탐색구간:',ny,'거리:',distance)
            dfs(nx,ny,first_x,first_y)

4방향 탐색중 현재 색깔이 다음 탐색할 구간의 색깔과 일치하고 아직 방문하지 않은 곳이면 거리를 하나 올려주며 재귀로 탐색해주도록 합시다.

    distance -= 1

마지막으로 그래프 깊숙히 탐색하다 더 들어갈 수 없다면 distance를 1씩 빼주면서 나와주도록 합시다.

출력

if boolean == True:
    print('Yes')
else:
    print('No')    

boolean값이 True일 경우 Yes를, False일 경우 No를 출력하면 정답이 나옵니다.