[BOJ 16724🥇3] 피리 부는 사나이(Python)

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

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

3 4
DLLL
DRLU
RRRU

예제 출력 1

2

다음과 같이 'SAFE ZONE'을 만들면 영과일 회원들이 지도 어느 구역에 있더라도 'SAFE ZONE'에 들어갈 수 있다.

 

⭕ CODE

import sys

sys.stdin = open('input.txt')


def dfs(x, y, idx):
    global count
    # 방문처리를 idx로
    visited[x][y] = idx

    if arr[x][y] == 'U':
        nx = x - 1
        ny = y
        # 방문한적이 없으면
        # 같은 idx로 dfs실행
        if visited[nx][ny] == 0:
            dfs(nx, ny, idx)
        # 다음이 같은 idx라면
        # 같은구역이므로 safezone 1개 있다
        elif visited[nx][ny] == idx:
            count += 1
            return
        # 방문한적있고 다른 구역이라면 
        # 이미 여기가 safezone임
        else:
            return
    elif arr[x][y] == 'D':
        nx = x + 1
        ny = y
        if visited[nx][ny] == 0:
            dfs(nx, ny, idx)
        elif visited[nx][ny] == idx:
            count += 1
            return
        else:
            return
    elif arr[x][y] == 'R':
        nx = x
        ny = y + 1
        if visited[nx][ny] == 0:
            dfs(nx, ny, idx)
        elif visited[nx][ny] == idx:
            count += 1
            return
        else:
            return
    elif arr[x][y] == 'L':
        nx = x
        ny = y - 1
        if visited[nx][ny] == 0:
            dfs(nx, ny, idx)
        elif visited[nx][ny] == idx:
            count += 1
            return
        else:
            return


# 구역을 구하는거라면 dfs를 사용해보자
n, m = map(int, input().split())

arr = [list(input()) for _ in range(n)]
visited = [[0] * m for _ in range(n)]

count = 0
idx = 1
for i in range(n):
    for j in range(m):
    	# 방문안했으면 dfs실행
        if visited[i][j] == 0:
            dfs(i, j, idx)
            # 다음구역을 위한 idx증가
            idx += 1
print(count)

✏️ Comment

처음에는 bfs로 접근했다. 지도밖으로 나가는 방향은 주어지지 않으므로 자기자신에서 출발해서 다시 자기자신으로 돌아오는 서클은 무조건 존재한다. 그 서클의 개수가 정답의 개수라고 생각하였고 아래와 같이 코드를 작성하였더니 시간초과가 났다. 거의 모든 배열을 탐색하고 bfs에서 종료조건에서 safezone에 더하기 위해서 for문을 또 돌리는게 시간을 많이 잡아먹은게 아닐까 추측한다.

from collections import deque

def bfs(x, y):
    global count, safezone
    xself = x
    yself = y
    q = deque()
    q.append((x, y))
    # 자기자신으로 돌아와야하므로 방문처리하지말자
    # 처음부터 q에 자기 자신이 담기니까 다른곳을 안들렀다는
    # flag를 0 으로 지정해주자
    flag = 0
    safe = []
    while q:
        x, y = q.popleft()

        # 자기 자신으로 돌아오면
        if x == xself and y == yself and flag == 1:
            count += 1
            visited[x][y] = 1
            for x,y in safe:
                safezone[x][y] = 1
            return safezone
        flag = 1
        if safezone[x][y] == 1:
            break
        if arr[x][y] == 'U':
            nx = x - 1
            ny = y
            if visited[nx][ny] == 0:
                visited[nx][ny] = 1
                q.append((nx, ny))
                safe.append((nx,ny))
        elif arr[x][y] == 'D':
            nx = x + 1
            ny = y
            if visited[nx][ny] == 0:
                visited[nx][ny] = 1
                q.append((nx, ny))
                safe.append((nx,ny))
        elif arr[x][y] == 'R':
            nx = x
            ny = y + 1
            if visited[nx][ny] == 0:
                visited[nx][ny] = 1
                q.append((nx, ny))
                safe.append((nx,ny))
        elif arr[x][y] == 'L':
            nx = x
            ny = y - 1
            if visited[nx][ny] == 0:
                visited[nx][ny] = 1
                q.append((nx, ny))
                safe.append((nx,ny))

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

arr = [list(input()) for _ in range(n)]
safezone = [[0] * m for _ in range(n)]
# visited = [[0]*m for _ in range(n)]

# 지도밖으로 나가는 방향은 주어지지 않으므로
# 자기자신에서 출발해서 다시 자기자신으로 돌아오는 서클은 무조건 존재
# 그 서클의 개수가 정답의 개수라고 생각
count = 0
for i in range(n):
    for j in range(m):
        visited = [[0] * m for _ in range(n)]
        # 방문한적없고 세이프존에도 없으면
        if visited[i][j] == 0 and safezone[i][j] == 0:
            bfs(i, j)
print(count)

위 방식으로는 불가능하다고 생각하여 어짜피 구역을 구하는거면 dfs로 문제를 해결하기위해 접근하는데 생각보다 아이디어가 잘 안떠올라서 다른 사람 블로그를 참고했다. 아래 블로그에서 처음 dfs는 1로 돌고 다 돌고나서 다음 dfs는 2로 돌면서 구역을 확인하는 아이디어를 얻고 코드를 만들었더니 최소 safe zone 개수를 구할 수 있었다,
https://one10004.tistory.com/302?category=875952

16724. 피리 부는 사나이 (Python)

 

• dfs 연습을 많이하자