[백준 16724번] 피리 부는 사나이

16724번: 피리 부는 사나이

import sys
sys.setrecursionlimit(10**5)
n,m = map(int,input().split())

area = [list(sys.stdin.readline().rstrip()) for _ in range(n)]

visited = [[-1]*m for _ in range(n)]

count = 0

index = 0

def dfs(x,y,idx):

    global count

    if visited[x][y] != -1:
        if visited[x][y] == idx:
            count += 1
        return
    
    visited[x][y] = idx

    if area[x][y] == "D":
        nx = x + 1
        ny = y
    elif area[x][y] == "R":
        nx = x
        ny = y + 1
    elif area[x][y] == "L":
        nx = x
        ny = y - 1
    elif area[x][y] == "U":
        nx = x - 1
        ny = y

    dfs(nx,ny,idx)

for i in range(n):
    for j in range(m):
        dfs(i,j,index)
        index += 1
for i in visited:
    print(i)
print(count)

이번 문제는 결론적으로 2차원 배열 내에서 사이클의 개수를 구하는 문제이다.

 

처음에는 방문처리 방식을 True/False로 처리하였는데 DFS를 사용해서 주어진 경로로 들어가다가 이미 방문한 좌표인 경우, 만약에 처음 시작한 좌표랑 다르다면 전부 Backtracking 으로 방문처리를 False로 재설정해주었다.

 

하지만 이렇게 방문처리를 T/F로만 처리하고 백트래킹을 해주면 이미 사이클을 형성할 수 없는 경로인데도 불구하고 다시 재방문하는 불필요한 연산을 하게 된다.

 

따라서 방문처리를 T/F가 아니라 index라는 숫자로 저장하여 방문한 경로마다 다른 인덱스를 부여하고, 같은 인덱스를 만났을 경우에 사이클의 개수로 카운팅해주었다. 이렇게 되면 같은 인덱스를 만나게 되었을 때 사이클을 형성하게 되므로 시작지점과 도착지점만 비교하는 것보다 훨씬 더 효율적으로 문제가 풀리게 된다.

 

배운 점 및 느낀 점

1. DFS/BFS 문제를 풀 때 방문여부를 체크하는 배열을 무조건 True/False로 지정하고 풀지말자.
2. 불필요한 반복 연산을 최소화해야 시간초과를 피할 수 있다.