[KAKAO] 동굴탐험 (2020 KAKAO 인턴십)

조만간 코딩 테스트가 있기도하고, 감이 좀 무뎌진것 같아 프로그래머스나 백준의 문제들을 풀었다.

 

요즘은 새로운 문제들을 풀기 앞서 좀 더 기초를 다지는 느낌으로 풀었던 문제들을 다시 효율적이고 빠르게 풀어보는

연습을 하고 있는 중이다.

 

옛날 C++로 풀었던 삼성 구현 문제들도 풀어보고, 카카오 관련 구현 + 알고리즘 문제들을 풀었다.

문제를 풀면서 느끼는 바로는 각 기업만의 색깔이 문제에서 묻어나는 듯 했다. 뭔가 삼성은 풀 집중력으로 어떻게든 디버깅과

구현을 한다면 풀 수 있는 느낌이 강했고, 카카오는 생각이 떠오르지 않으면 못 푸는 문제들도 있었고 효율성 문제들은

+a 까지 생각 해줘야하는 문제들이 많았다.

 

삼성 문제들을 풀면서 각 문제의 복잡한 요구사항들을 시뮬레이션 하며, 머릿속으로 그려보는 연습이 많이 되었다.

카카오 문제들은 위의 연습도 될 뿐 아니라, 문제 해결 능력이 길러진 느낌이었다.

 

물론 기업의 문제들이 아니더라도 이러한 부분을 기를 순 있었다. 물론 테스트케이스가 너무 빡빡하거나, 어찌보면 문제의 

요구사항들이 애매한 문제들은 풀면서 시간이 많이 아까웠던 것 같다.

 

그래서 그런지  더욱 기업 문제들을 많이 풀어보려 했던게 아닌가 싶다.. ㅎ

 

다시 기본기를 잡고 쉬운 문제들 부터 풀어보면서 이번엔 프로그래머스의 level4 문제를 풀어보았다.

역시 쉽게 풀리면 재미가 없나보다. 어제 밤에 친구들과 같이 풀다가 집중도 안되고 뭔가 잘 안 풀리지 않아 아침에 다시 풀어보고자 했다.

 

다행히 다시 문제를 보고 나니 생각보단 쉽게 풀렸다. 물론 두 가지 방법들을 시도 해봤는데, 하나는 실패.. ㅋㅋ

 

그럼 문제를 풀어보자.

 

programmers.co.kr/learn/courses/30/lessons/67260

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

 

문제를 맞이하면 조건들이 좀 어렵게 꼬여 있었다.

• 양방향으로 이어져 있는 방
• 서로 다른 두 방을 직접 연결하는 통로는 한 개
• 임의의 두 방의 최단거리는 한 가지 이동 불가능 한 방은 없음
• path 배열의 길이는 n-1

여기서 유추 할 수 있었던 것은 양방향 간선, 사이클 없음 두 가지 이다. 

방의 개수가 n 인 것과 path 배열의 길이가 n-1 인 것을 유추해 본다면 사이클이 없음을 알 수 있다.

 

먼저 방문해야하는 방이 있으므로 위상정렬일 것 같은 느낌이 들었다. 하지만 어떻게 응용을 해야할까..

 

그냥 위상정렬만 이용해서 노드에 추가하며 풀어 본 것 (틀림)

from collections import deque

def solution(n, path, order):
    answer = True
    
    node = [[] for i in range(n)]
    degree = [0 for i in range(n)]
    for p in path:
        start, end = p
        node[start].append(end)
        node[end].append(start)
    
    priority = [[] for i in range(n)]
    for o in order:
        before, after = o
        priority[before].append(after)
        degree[after] += 1
        
    if degree[0] > 0:
        return False
    
    q = deque()   
    check = [0 for i in range(n)]
    check[0] = 1
    q.append(0)
                            
    while q:
        vertax = q.popleft()
        for ver in node[vertax]:
            if check[ver] == 0 and degree[ver] == 0:
                check[ver] = 1
                q.append(ver)
        
        for ver in priority[vertax]:
            degree[ver] -=1
            if degree[ver] == 0:
                check[ver] = 1
                q.append(ver)
    
    return False if min(check) == 0 else True

 

 

간단한 문제를 보도록 해보자.

 

n = 5, orders = [2, 1] 이라 가정해보자. (path는 직접 그림으로 대체하겠다.)

 

예시 1

위상정렬대로 풀어보았을 때 위의 case는 통과 한다.

 

하지만, 이 문제를 보도록 해보자.

 

n = 6, path = [2, 4], [5, 1] 일때

예시 2

이렇게 되면 2번을 보았을 때 4번의 degree -= 1 이 되면서 4번의 degree = 0 이 되어 4번을 넣게 된다.

4번을 들어가기 위해선 1번을 들어가야 하고, 5번을 들어가야 1번을 들어갈 수 있으므로 여기서 예외 케이스가 발생한다.

 

여기서 고민을 했다가 떠오른 아이디어는 degree = 0 이 되는 순간 주변 노드를 탐색하며

주변 노드들 중 방문을 했었던 노드가 있는 지 검사를 해주고, 만약 방문 했었다면 그 노드는 들어갈 수 있으므로 deuqe에 넣어준다.

 

최종 코드

from collections import deque

def solution(n, path, order):
    answer = True
    
    node = [[] for i in range(n)]
    degree = [0 for i in range(n)]
    for p in path:
        start, end = p
        node[start].append(end)
        node[end].append(start)
    
    priority = [[] for i in range(n)]
    for o in order:
        before, after = o
        priority[before].append(after)
        degree[after] += 1
        
    if degree[0] > 0:
        return False
    
    q = deque()   
    check = [0 for i in range(n)]
    check[0] = 1
    q.append(0)
                            
    while q:
        vertax = q.popleft()
        for ver in node[vertax]:
            if check[ver] == 0 and degree[ver] == 0:
                check[ver] = 1
                q.append(ver)
        
        for ver in priority[vertax]:
            degree[ver] -=1
            if degree[ver] == 0:
                flag = False
                for v in node[ver]:
                    if check[v]:
                        flag = True
                        break
                if not flag:
                    continue
                check[ver] = 1
                q.append(ver)
    
    return False if min(check) == 0 else True

 

물론 더 좋은 코드가 있을 법 하지만, 여기까지 포스팅을 마무리 하겠다.