백준: 16929 Two Dots

문제

16929번: Two Dots

 

문제 풀이

  특정 지점을 시작으로 같은 색을 가진 싸이클이 있는지 확인하고 반환하는 문제이다. 따라서 특정 지점에서 DFS를 통해 상, 하, 좌, 우로 순회하되 같은 출발 지점과 같은 색인지와, 방문여부를 판단하게 되면 싸이클 여부를 확인 할 수 있다.

 

 DFS를 통해 탐색할 때 다음과 같이 진행하면 답을 찾을 수 있다.

• 상, 하, 좌, 우 탐색 시 0 <= x < n, 0 <= y < m과 같이 영역을 벗어나지 않는지 확인하여야 한다.
• 최소 싸이클을 이루는 점의 개수는 4개 이다.
  • 점의 개수가 4개 이상이고, 시작점으로 돌아온다면 싸이클이 있는 것이다.
• 백트랙킹이 필요하므로, 재귀 호출 후 원래 되로 초기화하여야 한다.

 

코드

from sys import stdin


def visitable(x, y):
    return 0 <= x < n and 0 <= y < m and not visited[x][y]


def dfs(cnt, start, cur, color):
    for x, y in dirs:
        next_x, next_y = cur[X] + x, cur[Y] + y

        # 4점 이상을 방문하고, 출발점과 같다면 싸이클이 있는 것이다.
        if cnt >= 4 and start == [next_x, next_y]:
            print('Yes')
            exit()

        if visitable(next_x, next_y) and graph[next_x][next_y] == color:
            visited[next_x][next_y] = True
            dfs(cnt + 1, start, [next_x, next_y], color)
            visited[next_x][next_y] = False


if __name__ == "__main__":
    answer = False
    X, Y = 0, 1
    n, m = map(int, stdin.readline().split())
    graph = [list(stdin.readline().strip()) for _ in range(n)]
    visited = [[False] * m for _ in range(n)]
    dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))

    for x in range(n):
        for y in range(m):
            if not visited[x][y]:
                visited[x][y] = True
                dfs(1, [x, y], [x, y], graph[x][y])

    print('No')