[프로그래머스] 동굴 탐험 파이썬

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/67260

코딩테스트 연습 - 동굴 탐험

백준에 비슷한 문제를 풀었던 적이 있어서 아이디어는 금방 떠올랐다.

백준 문제 링크 : https://www.acmicpc.net/problem/9328

9328번: 열쇠

 

 

이 문제도 다음 방으로 가는 열쇠가 어떤 방에 있다고 생각하고 풀었다.

그래서 order에는

(열쇠가 있는 방, 해당 열쇠로 열수 있는 방)

이런식으로 생각하고 풀었다.

 

우선 처음에는 효율성 마지막에서 시간초과가 났다.

처음에는 bfs를 돌다가 아직 열려있지 않은 칸이면 그대로 큐에 남겨뒀다.

이것이 엄청 쌓여서 시간초과가 난듯 하다. 그래서 잠겨있는 칸을 방문하고 해당 칸에 문이 열렸을 때만 큐에 넣어서 해결했다.

 

우선 주어신 path를 인접 리스트로 바꿨다.

다음 크게 3개의 배열을 사용 했다.

key, door, wating

key는 해당 번호의 방에 어떤 방의 열쇠가 들어있는지 저장하고 없다면 -1을 갖는다.

door는 현재 칸이 열려있는지 잠겨 있는지를 나타낸다. True : 잠김, False 열림

wating는 현재 칸이 잠겨있어서 열쇠로 문이 열릴 때 까지 기다리는 배열이다.

      True - 잠겨서 기다리고 있는 칸, False 기다리지않고 있는 칸

       True에서 False로 바뀌면 큐에 넣어서 진행

 

그리고 BFS를 수행했다.

 

주의할 것은 시작점에도 열쇠가 있을 수 있고 잠겨 있을 수 있다.

이를 우선 체크 한다.

 

다음 이제 큐가 빌때까지 돈다.

 

우선 현재 점에 열쇠가 있는지 체크한다.

만약 열쇠가 있는 칸이라면 해당칸의 열쇠로 열수 있는 door의 칸을 열어주자. 즉 값을 False로 바꿔주자.

그리고 해당 door의 칸의 wating값이 True라면 이미 BFS를 진행하다. 해당 칸의 wating의 값이 True라면 door여서 더이상 진행하지 못하고 있는 칸이다. 따라서 key로 door칸을 열어줬으므로 해당칸은 진행할 수 잇는 상황인것이다. 따라서 큐에 넣어주자.

 

이제 현재 칸에 연결된 방들을 봐본다.

우선 방문했는지 체크한다.

그리고 그 칸이 문인지 아닌지 확인한다.

문이라면 더이상 진행할 수 없으므로 wating에서 해당 칸의 값을 True로 표시한다. 이것은 문이므로 열릴때 까지 기다린다는 것이다.

문이 아니라면 방문 표시하고 큐에 넣자.

 

BFS 진행시 반복문을 두개로 감쌌다.

가장 바깥은 큐가 빌때까지 돈다.

그 다음 반복문은 현재 사이클에서 큐의 길이만큼 돈다.

이것은 현재 큐에 있는 칸들이 모두 잠겨 있는 방이이서 더이상 진행할 수 없는 상황을 체크하기 위함니다.

그래서 flag변수를 두고 반복문을 돌 동안 한번이라도 다음 칸으로 진행이 됐다면 다음 사이클로 진행하면 된다.

하지만 그렇지 않다면 모두 잠겨있는 칸이므로 BFS를 종료하면된다.

 

 

마지막 답 도출이다.

나는 BFS 돌다가 열려있는 칸을 방문할 때 카운팅을 해주었다. 이때 카운팅 값이 모든 방의 개수와 같다면 True, 아니면 False로 판별했다.

 

from collections import deque


def solution(n, path, order):
    adj_list = set_adj_list(n, path)
    key, door = set_key_door(n, order)
    return bfs(n, adj_list, key, door)


def bfs(n, adj_list, key, door):
    wating = [False] * n
    visited = [False] * n
    q = deque([0])

    visited[0] = True
    count = 0
    if door[0]:
        return False
    
    if key[0] > 0:
        door[key[0]] = False
        key[0] = -1
    while q:
        q_len = len(q)
        flag = False
        for _ in range(q_len):
            now = q.pop()

            if key[now] > 0:
                door[key[now]] = False
                if wating[key[now]]:
                    wating[key[now]] = False
                    q.appendleft(key[now])
                    visited[key[now]] = True
                key[now] = -1

            flag = True
            count += 1
            for nxt in adj_list[now]:
                if not visited[nxt]:
                    if door[nxt]:
                        wating[nxt] = True
                    else:
                        visited[nxt] = True
                        q.appendleft(nxt)
        if not flag:
            break
    return True if count == n else False


def set_key_door(n, order):
    key = [-1] * n
    door = [False] * n

    for a, b in order:
        key[a] = b
        door[b] = True
    return key, door


def set_adj_list(n, path):
    adj_list = [[] for _ in range(n)]
    for a, b in path:
        adj_list[a].append(b)
        adj_list[b].append(a)

    return adj_list