BOJ :: [16929] Two dots

문제

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

16929번: Two Dots

 

문제 설명

Two dots게임은 같은 색을 가진 노드를 이어서 사이클을 만드는 게임이다. 게임판의 크기는 최대 50 x 50이며 각 노드는 알파벳으로 주어진다. 즉 알파벳이 같다면 같은 색으로 간주한다. 주어진 게임판에서 사이클이 존재하면 Yes를, 존재하지 않으면 No를 출력한다.

 

문제 풀이

dfs로 풀이할 수 있다. 먼저 (0, 0)부터 (n-1, n-1)까지 dfs로 탐색하면서 사이클이 존재하는지 검사한다. dfs를 탐색할 때 상, 하, 좌, 우 4방향으로 탐색하며, 이동할 곳이 같은 색인 경우 다음 경로로 이동한다. 이미 방문한 곳을 다시 방문한다면 사이클이 존재한다는 의미이기 때문에 dfs를 탐색하면서 이미 방문한 노드를 다시 방문하는 경우 Yes를 출력하고 종료한다. 상, 하, 좌, 우로 이동하는 중 직전에 방문한 곳을 다시 방문하는 경우 방문한 곳을 다시 방문하여 사이클로 간주할 수 있기 때문에 이전 좌표를 함께 보내서 이전 좌표로 방문하는 경우 사이클로 간주하지 않도록 구현했다. 

 

코드

import sys
input = sys.stdin.readline

# x, y는 현재 좌표
# sx, sy는 움직이기 직전 좌표
def dfs(x, y, sx ,sy):
    a = table[x][y]
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

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

        if nx < 0 or ny < 0 or nx >= n or ny >= m or a != table[nx][ny] or (nx == sx and ny == sy):
            continue
        
        if visit[nx][ny] == True:
            return True
        
        visit[nx][ny] = True
        result = dfs(nx, ny, x, y)

        if result:
            return True

    return False

n, m = map(int, input().split())

table = [[] for _ in range(n)]

for i in range(n):
    table[i] = input()

visit = [[False for _ in range(m)] for _ in range(n)]

flag = False
for i in range(n):
    for j in range(m):
        if visit[i][j]:
            continue
        visit[i][j] = True
        result = dfs(i, j, i, j)

        if result:
            flag = True
    if flag:
        break

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

 

작성한 글에 잘못된 부분이나 문제가 있는 경우 댓글에 작성해 주시면 수정하도록 하겠습니다 . 질문도 환영합니다! :)