[프로그래머스] 67260. 동굴 탐험

2020 카카오 인턴십 - 67260. 동굴 탐험

Python 풀이

 

풀이

복잡한 알고리즘을 생각할 필요 없이,

BFS로 탐색하면서 order (방문 순서) 만 처리해 주면 된다고 생각했다.

그리고 효율성을 위해 방문 체크는 Hash로 구성된 Set을 이용.

 

근데.. 각 루프마다 False 체크를 하니까 시간초과가 난다.

def A():
    for room in rooms:
        if room not in follow:
            return False
    return True

얘 때문 맞는듯..

 

Code

from collections import deque
def solution(n, path, order):
    pre = [i[0] for i in order]
    follow = [i[1] for i in order]

    visit = set([0])
    rooms = deque([0])
    graph = {i: [] for i in range(n)}

    for p in path:
        graph[p[0]].append(p[1])
        graph[p[1]].append(p[0])



    def A():
        for room in rooms:
            if room not in follow:
                return False
        return True


    while rooms:

        if A():
            return False
            break

        room = rooms.popleft()

        # 선행 이행 X
        if room in follow:
            rooms.append(room)
        # 걸리는 조건이 없을 때
        else:
            visit.add(room)
            # 선행조건 해결
            if room in pre:
                i = pre.index(room)
                del pre[i]
                del follow[i]

            for n in graph[room]:
                if n not in visit and n not in rooms and n != room:
                    rooms.append(n)


    return True

 

 

풀이 2

개선되긴 하였으나.. 아직 시간초과 남.

Code

from collections import deque
def solution(n, path, order):
    pre = [i[0] for i in order]
    follow = [i[1] for i in order]

    visit = set([0])
    rooms = deque([0])
    rooms_wait = set()  # 선행조건때문에 못 가는 방 넣어두기
    graph = {i: [] for i in range(n)}

    for p in path:
        graph[p[0]].append(p[1])
        graph[p[1]].append(p[0])


    while rooms:
        room = rooms.popleft()

        # 선행 이행 X
        if room in follow:
            rooms_wait.add(room)
        # 걸리는 조건이 없을 때
        else:
            visit.add(room)
            # 선행조건 해결
            if room in pre:
                i = pre.index(room)
                del pre[i]
                if follow[i] in rooms_wait:
                    rooms.append(follow[i])
                    rooms_wait.remove(follow[i])
                del follow[i]

            for n in graph[room]:
                if n not in visit and n not in rooms and n != room:
                    rooms.append(n)

    if rooms_wait:
        return (False)
    else:
        return (True)

 

풀이 3

pre와 follow를 dictionary로 바꿔 시간단축을 꾀했고,

for n in graph[room]:
    if n not in visit and n not in rooms and n != room:
        rooms.append(n)

여기서 시간 소모가 많이 되는 것 같아 아래처럼 수정.

for n in graph[room]:
    if n not in visit and n not in rooms_wait and n != room:
        rooms.append(n)

그렇게 성공.

 

Code

from collections import deque
def solution(n, path, order):
    pre = {i[0]: i[1] for i in order}
    follow = {i[1]: i[0] for i in order}

    visit = set([0])
    rooms = deque([0])
    rooms_wait = set()  # 선행조건때문에 못 가는 방 넣어두기
    graph = {i: [] for i in range(n)}

    for p in path:
        graph[p[0]].append(p[1])
        graph[p[1]].append(p[0])


    while rooms:
        room = rooms.popleft()

        # 선행 이행 X
        if room in follow:
            rooms_wait.add(room)
        # 걸리는 조건이 없을 때
        else:
            visit.add(room)
            # 선행조건 해결
            if room in pre:
                i = pre[room]
                del pre[room]
                if i in rooms_wait:
                    rooms.append(i)
                    rooms_wait.remove(i)
                del follow[i]

            for n in graph[room]:
                if n not in visit and n not in rooms_wait and n != room:
                    rooms.append(n)

    if rooms_wait:
        return (False)
    else:
        return (True)