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

🔈 문제

피리 부는 사나이 성우는 오늘도 피리를 분다.

성우가 피리를 불 때면 영과일 회원들은 자기도 모르게 성우가 정해놓은 방향대로 움직이기 시작한다. 성우가 정해놓은 방향은 총 4가지로 U, D, L, R이고 각각 위, 아래, 왼쪽, 오른쪽으로 이동하게 한다.

이를 지켜보던 재훈이는 더 이상 움직이기 힘들어하는 영과일 회원들을 지키기 위해 특정 지점에 ‘SAFE ZONE’ 이라는 최첨단 방음 시설을 만들어 회원들이 성우의 피리 소리를 듣지 못하게 하려고 한다. 하지만 예산이 넉넉하지 않은 재훈이는 성우가 설정해 놓은 방향을 분석해서 최소 개수의 ‘SAFE ZONE’을 만들려 한다. 

성우가 설정한 방향 지도가 주어졌을 때 재훈이를 도와서 영과일 회원들이 지도 어느 구역에 있더라도 성우가 피리를 불 때 ‘SAFE ZONE’에 들어갈 수 있게 하는 ‘SAFE ZONE’의 최소 개수를 출력하는 프로그램을 작성하시오.

 

📝입력

첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다.
두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주어진다.
지도 밖으로 나가는 방향의 입력은 주어지지 않는다.

 

📑출력

첫 번째 줄에 ‘SAFE ZONE’의 최소 개수를 출력한다.

 

📚 문제 풀이

 

보드에 적혀진 U, D, L, R로 탐색하되 이때 싸이클의 갯수를 구하는 문제였다.

U,D,L,R을 키값으로 둔 딕셔너리를 사용하여 문자열을 바로 이동 방향으로 변경하였고, 이전에 방문한 적이 없는 곳을 찾아 DFS를 하였다. 그 이전에 방문한 적이 없는 곳이 하나의 사이클로 합쳐질 수 있는 곳이라면 카운트를 하지 않았고, 새로운 사이클이면 카운트를 해주었다.

 

무슨 말이냐하면,,

3 3
RDD
ULD
ULL

위와 같은 예제가 있다.

이중 반복문을 사용해서 방문하지 않은 곳을 찾기 때문에, 제일 처음에 탐색하게 되는 곳은 0,0 즉 R이다.

여기서 탐색을 시작하면 

 

예제 1

이런 식으로 한번 탐색을 하게 된다. (역 ㄷ 모양)

그리고 다음으로 방문하지 않은 곳은 0,2 즉 D 이다.

여기서 다시 탐색을 하면

 

예제 1

이렇게 탐색을 한다. 

사실 두개 모두 한 사이클이다. 방문하지 않은 곳만 방문하기 때문에 0,1 직전에 탐색을 멈췄다. 이 두개를 하나의 카운트로 처리해주는 것이 중요했다. 탐색을 멈췄을 때 마지막 방문위치가 이전 탐색에서 방문한 부분이면 한 사이클로 이을 수 있기 때문에 카운트 하지 않았고, 현재 탐색에서 방문한 곳이라면 새로운 사이클이기 때문에 카운트 해주었다.

 

 

💻 코드

import sys
input = sys.stdin.readline
 
d = {"U":[-1,0], "D":[1,0], "R":[0,1], "L":[0,-1]}
 
def search(y, x, idx):
    while not visited[y][x]:
        visited[y][x] = idx
        y,x = y+d[board[y][x]][0], x+d[board[y][x]][1]
    
    if visited[y][x] == idx:
        return 1
    return 0
 
n,m = map(int,input().split())
board = [list(map(str,input().rstrip())) for _ in range(n)]
visited = [[0]*m for _ in range(n)]
ans = 0
idx = 1
for i in range(n):
    for j in range(m):
        if not visited[i][j]:
            ans += search(i,j,idx)
            idx += 1
print(ans)

 

🍭 시행착오

처음에 틀렸던 이유는 앞서 설명한 같은 사이클을 여러번 카운트해줬기 때문이었다.

 

🔗 문제링크 피리 부는 사나이

16724번: 피리 부는 사나이