[프로그래머스 > Lv4] 동굴탐험

프로그래머스

 

1. 문제

유일한 입구는 0번 방과 연결되어 있습니다. 각 방들은 양방향으로 통행이 가능한 통로로 서로 연결되어 있는데,

서로 다른 두 방을 직접 연결하는 통로는 오직 하나입니다.

 

1. 모든 방을 적어도 한 번은 방문해야 합니다.
2. 특정 방은 방문하기 전에 반드시 먼저 방문해야 하는 방이 정해져 있습니다.

 

[입력]

• 방 개수 n
• 동굴의 각 통로들이 연결하는 두 방의 번호가 담긴 2차원 배열 path
• 프로도가 정한 방문 순서가 담긴 2차원 배열 order

[결과]

프로도가 규칙에 맞게 모든 방을 탐험할 수 있을 지 true / false return

 

2. 풀이

처음은 간단하게 BFS를 이용해 풀었지만, ㅎㅎ 효율성 테스트 9,10번이 어떻게 해도 시간초과가 발생해

로직을 약간 수정하게 되었습니다.

 

가장 먼저 입력으로 들어온 정보들을 사용하기 쉽도록 수정해줄 필요가 있습니다.

2.1 각 방들의 연결관계

maps = [[] for _ in range(n)] # 방들의 연결관계
for s, e in path:
    maps[s].append(e)
    maps[e].append(s)

 

2.2 선 방문 관계

제 풀이에서는 A -> B일 때,

• A를 방문했을 때 갈 수 있는 방의 번호
• B를 방문하기 위해 들려야 하는 방의 번호

이 두 정보가 모두 필요하기 때문에, 각 정보를 별도로 저장하는 배열 2개를 사용하였습니다.

# pre_room[i]: i를 방문하기 위해 선방문해야 방
pre_room = [0] * n
# next_room[i]: i를 방문한 이후 다음에 방문할 수 있는 방
next_room = [0] * n 
for s, e in order:
    pre_room[e] = s
    next_room[s] = e​

 

2.3 BFS

이후에는 BFS 알고리즘을 사용해 0번 방부터 차례대로 각 방들을 방문해주면 됩니다.

위와 같은 순서로

1. A를 방문했을 때 갈 수 있는 방이 이미 BFS에서 방문했던 방이라면(unreachable[i]의 값이 true) 해당 방을 queue에 추가해줍니다.
2. A를 통해서 방문할 수 있는 방(예에서는 C,D,E) 중에서 지금 바로 방문이 가능한 방은 queue에 추가해줍니다.
3. 바로 방문이 불가능하고, 다른 방을 먼저 들린 이후에 가능한 방인 경우 unreachable 배열에 해당 방의 값을 true로 변경해줍니다.

위와 같이 수행하였을 때, 이전에 방문하지 못한 방을 차후에 다시 재방문할 수 있으며

시간 복잡도로도 n밖에 소요되지 않기 때문에 시간 내에 수행될 수 있습니다. 👍🏻

 

3. 코드

Python

def solution(n, path, order):
    maps = [[] for _ in range(n)] # 방들의 연결관계
    for s, e in path:
        maps[s].append(e)
        maps[e].append(s)
        
    # pre_room[i]: i를 방문하기 위해 선방문해야 방
    pre_room = [0] * n
    # next_room[i]: i를 방문한 이후 다음에 방문할 수 있는 방
    next_room = [0] * n 
    for s, e in order:
        pre_room[e] = s
        next_room[s] = e
    
    # 0번 방을 처음부터 방문하지 못하는 경우 처리 필요
    if pre_room[0] != 0: return False
    
    q = [0]
    unreachable = [False] * n
    visited = [False] * n
    visited[0] = True
    
    while q:
        room = q.pop(0)
        
        if unreachable[next_room[room]]:
            q.append(next_room[room])
            unreachable[next_room[room]] = False
        
        visited[room] = True
        for e in maps[room]:
            if not visited[e]:
                if visited[pre_room[e]]: q.append(e)
                else: unreachable[e] = True
    
    return all(visited)

 

---

[풀이 노트]