백준_16724_피리 부는 사나이

문제

16724번: 피리 부는 사나이

풀이

1) 문제 이해하기

• 지도 밖으로 나가는 방향은 주어지지 않으므로, 어느곳에서 시작하더라도 사이클을 만나게 된다. (경로의 끝은 항상 사이클이다.)
• SAFE ZONE을 각 사이클에 만든다면, SAFE ZONE을 최소한으로 설치할 수 있다. 
• 사이클의 개수를 출력한다. (최소 SAFE ZONE 개수 = 사이클의 개수) 

2) 사이클 찾기

모든 위치에서 dfs를 통해 성우가 피리를 불때 움직일 경로를 시뮬레이션한다.

1. 기존에 방문하지 않은 장소라면,

• 방문기록을 남긴다.
• 다음 장소로 이동한다.

2. 기존에 방문한 장소라면,

2-1. 현재 경로(시작 장소에서 현재장소에 이르기까지의 경로)에 존재하는 장소라면, 새로운 사이클을 찾은 것이다.

2-2. 현재 경로에 존재하지 않는 장소라면, 기존 사이클과 연결되는 경로이다.

코드

import sys
sys.setrecursionlimit(10**6)

def dfs(nr, nc) :
    cmm = board[nr][nc]
    board[nr][nc] = PASSED  # visited

    # 이미 지난 적 있는 노드에 도착
    if cmm not in dirDict :
        # 새로운 사이클을 발견함
        for tr, tc in visited[::-1] :
            if (tr, tc) == (nr, nc) : return True

        # 기존에 발견한 사이클과 연결됨
        return False


    visited.append((nr, nc))
    dr, dc = dirDict[cmm]
    return dfs(nr+dr, nc+dc)

PASSED = "P"
N, M = map(int, input().split())
board = [input() for i in range(N)]
board = [list(row) for row in board]

dirDict = dict()
dirDict["U"] = (-1, 0)
dirDict["D"] = (1, 0)
dirDict["L"] = (0, -1)
dirDict["R"] = (0, 1)

visited = list() # 사이클 여부를 판별하기 위해 저장
cnt = 0

for i in range(N) :
    for j in range(M) :
        cnt += dfs(i,j)
        visited.clear()

print(cnt)

마무리

위 풀이에서는 새로운 사이클인지 판별하기 위해, 현재 경로에서 해당 장소를 지났는지 확인하고 있다. 그렇다면, 모든 경로를 리스트로 저장하는 방법 말고도 더 효율적인 방법이 있을 것 같았다. 아래 코드처럼 경로를 시작할때 PASSED(방문한 적 있음을 나타내는 플래그)에 유일한 값을 부여한다면, 현재 노드를 현재 경로에서 방문했는지 체크 할 수 있다. (아래 코드로도 테스트 케이스들을 통과함을 확인했다.)

import sys
sys.setrecursionlimit(10**6)

def dfs(nr, nc) :
    cmm = board[nr][nc]

    # 이미 지난 적 있는 노드에 도착
    if cmm not in dirDict :
        if cmm == PASSED : return True # 새로운 사이클을 발견함
        return False # 기존에 발견한 사이클과 연결됨

    board[nr][nc] = PASSED  # visited
    dr, dc = dirDict[cmm]
    return dfs(nr+dr, nc+dc)

N, M = map(int, input().split())
board = [input() for i in range(N)]
board = [list(row) for row in board]

dirDict = dict()
dirDict["U"] = (-1, 0)
dirDict["D"] = (1, 0)
dirDict["L"] = (0, -1)
dirDict["R"] = (0, 1)
cnt = 0

for i in range(N) :
    for j in range(M) :
        PASSED = int("%04d%04d"%(i, j)) # 유일한 값을 부여
        cnt += dfs(i,j)

print(cnt)