백준 - 16929번: Two Dots (Python)

목차

• 문제명
• 문제풀이
• 코드

 

백준 - 16929번 : Two Dots 

 

문제 유형 : DFS, 그래프 탐색

난이도 : 골드 4

 

https://www.acmicpc.net/problem/16929

16929번: Two Dots

 

 

 

문제 풀이

 

모든 정점에 대하여

 

1. 주어지는 게임판과 동일한 넓이, 높이의 배열을 선언하고 

 

2. dfs로 그래프를 탐색하면서 시작점에서 몇번째로 탐색한 정점인지를 기록합니다.

 

3. 탐색이 끝나면 시작점 주위에 값이 4 이상인 값이 있다면 싸이클이 있는것이므로 "Yes" 출력

 

4. 모든 정점에 대하여 탐색하여도 싸이클이 없다면 "No" 출력

 

 

 

코드

 

import sys
input = sys.stdin.readline

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]


def dfs(r, c, color):
    for i in range(4):
        nr, nc = r + dr[i], c + dc[i]
        if 0 <= nr < N and 0 <= nc < M:
            if graph[nr][nc] == color and visit[nr][nc] == 0:
                visit[nr][nc] = visit[r][c] + 1
                dfs(nr, nc, color)


N, M = map(int, input().split())
graph = [list(input().strip()) for _ in range(N)]

for r in range(N):
    for c in range(M):
        visit = [[0] * M for _ in range(N)]
        visit[r][c] = 1
        dfs(r, c, graph[r][c])

        for i in range(4):
            nr, nc = r + dr[i], c + dc[i]
            if 0 <= nr < N and 0 <= nc < M:
                if visit[nr][nc] >= 4:
                    print("Yes")
                    sys.exit(0)

print("No")

 

 

 

마무리