[백준] 16929번 Two Dots - Python / 알고리즘 기초 2/2 - 그래프 1 (연습)

ByungJik_Oh·2025년 4월 14일

Baekjoon Online Judge

[Baekjoon Online Judge]

목록 보기

111/244

💡 문제

Two Dots는 Playdots, Inc.에서 만든 게임이다. 게임의 기초 단계는 크기가 N×M인 게임판 위에서 진행된다.

각각의 칸은 색이 칠해진 공이 하나씩 있다. 이 게임의 핵심은 같은 색으로 이루어진 사이클을 찾는 것이다.

다음은 위의 게임판에서 만들 수 있는 사이클의 예시이다.

점 k개 d $_1$ , d $_2$ , $...$ , d $_k$ 로 이루어진 사이클의 정의는 아래와 같다.

모든 k개의 점은 서로 다르다.
k는 4보다 크거나 같다.
모든 점의 색은 같다.
모든 1 ≤ i ≤ k-1에 대해서, d $_i$ 와 d $_{i+1}$ 은 인접하다. 또, d $_k$ 와 d $_1$ 도 인접해야 한다. 두 점이 인접하다는 것은 각각의 점이 들어있는 칸이 변을 공유한다는 의미이다.

게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구해보자.

입력

첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문자 한 글자이다.

출력

사이클이 존재하는 경우에는 "Yes", 없는 경우에는 "No"를 출력한다.

💭 접근

모든 점에 대해서 DFS를 호출하여 어떤 한 점에대해 출발하여 다시 어떤 점의 인접한 점이 시작점과 같다면 사이클이 만들어질 수 있는 것이다. 이때 주의할 점이 있는데, 시작점 바로 다음점은 시작점과 반드시 인접해 있기 때문에 최소 2개 이상의 점을 거쳤는지 확인 후, 2개 이상의 점을 거친 후 인접한 점 중 하나가 시작점이라면 사이클이 만들어질 수 있는 것이다.

📒 코드

import sys
sys.setrecursionlimit(10**6)

def dfs(x, y, depth):

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

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

        if nx == first[0] and ny == first[1] and depth > 2:
            print('Yes')
            sys.exit()

        if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and graph[nx][ny] == first[2]:
            visited[nx][ny] = True
            dfs(nx, ny, depth + 1)
            visited[nx][ny] = False

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

for i in range(n):
    for j in range(m):
        if not visited[i][j]:
            first = [i, j, graph[i][j]]
            visited[i][j] = True
            dfs(i, j, 0)
            visited[i][j] = False
print('No')