(Python/🥇3)백준알고리즘 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’의 최소 개수를 출력한다.
 
풀이:
 
시도1. 
 

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n, m = map(int, input().split())
board = [list(map(str,input())) for _ in range(n)]

move = {"D": (1, 0), "U": (-1, 0), "R": (0, 1), "L": (0, -1)}
def bfs(x,y):
    # 방문 처리 해주고
    visited[x][y] = True
    now = board[x][y]
    dx, dy = move[now]
    nx = dx + x; ny = dy + y
    if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
        visited[nx][ny] = True
        bfs(nx, ny)
    # 방문 할 곳 없으면
    else:
        return

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

count = 0 # safe zone
for x in range(n):
    for y in range(m):
        # 방문 안 했을 경우
        if not visited[x][y]:
            # 세이프 존 만들러 출발
            # print(x, y, visited, board[x][y])
            bfs(x,y)
            count += 1

print(count)

 
나는 단순히 구역만 나눴다.
어차피 D, L, R, U 으로 나누어져 있으니깐 문제로 예를들면
 
구역 1

구역 2.

 
이렇게 두 구역으로 말이다.
 
구역 안에서 어느 숫자로 시작하든 상관 없으므로
(0,0) 부터 시작해서 구역을 만들고, 이미 만드는데 지나간 곳은 visitied 로 방문 처리 해주었다.
 
하지만 틀리다.
 
구역을 나눠야 한다는 접근 방법은 맞지만, 사이클을 만들때 다른 사이클로 인식해서 갯수가 늘어난다.
만약 싸이클 두개가 합쳐지면 새로운 것을 안 만들어도 된다는 것이다. 예를들어
 
DLLL
RURU
이면
 

 
두 구역이 나오는거 같지만
 
왼쪽 초록 구역을 1로 하고 오른쪽을 2로 했을때
만약 2를 돌다가 1과 만나게 되면 2와 1은 합쳐지는 것이다.
즉 1개의 세이프존만 있으면 된다

풀이2: 
 

import sys

n, m = map(int, input().split())
board = [list(map(str,input())) for _ in range(n)]
move = {"D": (1, 0), "U": (-1, 0), "R": (0, 1), "L": (0, -1)}

def dfs(x,y, zone):
    # 방문 처리 해주고
    visited[x][y] = zone
    
    # 다음 방문할 곳
    now = board[x][y]
    dx, dy = move[now]
    nx = dx + x; ny = dy + y
    
    # 방문하지 않은 구역
    if visited[nx][ny] == -1:
        # 다음 좌표로 이동
        dfs(nx, ny, zone)
    
    # 방문 한 구역
    # 다 돌고 돌아옴 즉 싸이클 형성, 어디서 시작되든 상관없이 결국 싸이클 생성됨
    elif visited[nx][ny] == zone:
    	# 싸이클 생성
        global count
        count += 1
        return
    # 방문 을 했는데 다른 구역 숫자가 있다. ex) 2번 존이 L로 이동할때 1번 존과 만나면 둘이 연결됨 
    # 즉 둘이 연결된다 >> 세이프존 안 만들어도 된다
    else:
        return

visited = [[-1] * m for _ in range(n)]
count = 0; zone = 0

for x in range(n):
    for y in range(m):
        # 방문 안했으면
        if visited[x][y] == -1:
            # x, y, safezone 0 부터 순서대로 올라감
            dfs(x, y, zone)
            # 다음 safe zone
            zone += 1
print(count)

 
 
풀이3:

분리집합을 사용한다(Disjoint Sets) 

union - find 를 사용해도 가능할 것 같다. 하지만 원래 idx로 부모를 저장했는데 위와 같이 좌표이면 어떤것을 저장해야 할지 잘 모르겠다.
다른 분의 코드를 가져왔다.
 
https://velog.io/@sunkyuj/python-%EB%B0%B1%EC%A4%80-16724-%ED%94%BC%EB%A6%AC-%EB%B6%80%EB%8A%94-%EC%82%AC%EB%82%98%EC%9D%B4

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

 
https://imksh.com/60#article-1-3--%EC%96%B4,-%EC%A2%8C%ED%91%9C%EA%B0%92%EC%9D%B8%EB%8D%B0-%EC%96%B4%EB%96%BB%EA%B2%8C-union-find%EB%A5%BC-%EC%A0%81%EC%9A%A9%ED%95%98%EC%A7%80?

백준 16724 피리 부는 사나이 python