[백준] 15559번 - 내 선물을 받아줘 (Python)

문제

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

15559번: 내 선물을 받아줘

 

접근 방법

모든 장소에서 한 방향으로 이동할 수 있음이 보장되므로, 어느 지점에서 이동을 시작하든 계속 이동하다보면 사이클을 만들거나 중간에 사이클로 이동하는 형태가 된다.

각 사이클 안에 선물을 하나만 두면 해당 경로 모두 선물을 가져갈 수 있고, 이때가 최소 선물 개수가 된다.

 

상세

지도를 보면 각 장소에서 반드시 하나의 방향으로만 이동할 수 있고, 이로 인해 어떤 곳에서 시작하든 결국에는 사이클을 만드는 형태가 된다.

예를 들어 테스트 케이스의 예시를 화살표로 나타내면 다음과 같다 (SWWW/SEWN/EEEN)

위와 같이 총 2개의 큰 사이클이 만들어지고, 따라서 사이클 안에 하나씩 선물을 두면 최소 개수로 모든 곳에서 선물을 가질 수 있다.

 

그런데 주의해야할 사항이 있는데,

위의 예시에서 (0,2)에서 시작하는 경우와 같이, 직접 사이클을 만드는 것이 아니라 사이클로 이동하는 형태가 될 수도 있다.

이 경우 역시 사이클 하나당 선물을 하나씩 두면 모든 경로에서 선물을 가져갈 수 있다는 점은 동일하나,

모든 칸을 순차적으로 탐색했을 때 (0,0)에서 탐색 시작해서 [(0,0), (0,1), (1,0), (1,1)]의 사이클을 탐색해놓고 (0,2)에서 탐색 시작 시 아직 방문하지 않았다고 새로운 사이클로 판단하면 안된다는 이야기이다.

 

코드

import sys

N, M = map(int, sys.stdin.readline().rstrip().split())
mapArr = []
visited = [[False for _ in range(M)] for _ in range(N)]

di = {"N": -1, "E": 0, "W": 0, "S": 1} # ex. di["N"]는 (i, j)에서 N방향 이동시 i의 변화량
dj = {"N": 0, "E": 1, "W": -1, "S": 0}
answer = 0

for i in range(N):
    mapArr.append(list(sys.stdin.readline().rstrip()))

for i in range(N):
    for j in range(M):
        # 방문한 칸이면 패스
        if visited[i][j]:
            continue
        
        # 현재 탐색하는 곳에서 방문하는 위치들
        currentPath = set()
        
        # 방문하지 않은 각 칸이 나올 때까지 계속 이동하며 탐색
        currentI, currentJ = i, j
        while True:
            if visited[currentI][currentJ]:
                # 현재 탐색하는 곳 내에서 사이클이 이루어지는 경우 한 묶음이 추가된다.
                # "(사이클)<-<-" 과 같이 그 전에 이미 탐색한 사이클을 향하는 경로에 대해서는 한 묶음이 추가되지 않는다.
                if (currentI, currentJ) in currentPath:
                    answer += 1
                break
                
            visited[currentI][currentJ] = True
            currentPath.add((currentI, currentJ))
            
            currentPos = mapArr[currentI][currentJ] # 현재 위치한 알파벳
            currentI += di[currentPos]
            currentJ += dj[currentPos]
            
print(answer)

 

풀이 정보

시도 횟수: 2회

- 1회차 시도 WA 원인: 위 설명의 주의사항처럼 이미 탐색한 사이클을 구분하지 않았다.

총 문제 풀이에 걸린 시간: 25분 58초