프로그래머스 - 방의 개수 (그래프) / Level 5

출처 : https://programmers.co.kr/learn/courses/30/lessons/49190

코딩테스트 연습 - 방의 개수

 

문제 설명

원점(0,0)에서 시작해서 아래처럼 숫자가 적힌 방향으로 이동하며 선을 긋습니다.

ex) 1일 때는 오른쪽 위로 이동

그림을 그릴 때, 사방이 막히면 방 하나로 샙니다.
이동하는 방향이 담긴 배열 arrows가 매개변수로 주어질 때, 방의 개수를 return 하도록 solution 함수를 작성하세요.

 

 

제한사항

• 배열 arrows의 크기는 1 이상 100,000 이하입니다.
• arrows의 원소는 0 이상 7 이하입니다.
• 방은 다른 방으로 둘러 싸여질 수 있습니다.

 

입출력 예시

arrows	return
[6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0]	3

입출력 예 설명

• (0,0)부터 시작해서 6(왼쪽)으로 3번 이동합니다. 그 이후 주어진 arrows를 따라 그립니다.
• 삼각형 (1), 큰 사각형(1), 평행사변형(1) = 3

 

풀이

import collections


def solution(arrows):
    answer = 0
    move = [(-1, 0), (-1, 1), (0, 1), (1, 1),
            (1, 0), (1, -1), (0, -1), (-1, -1)]
    now = (0, 0)

    # visited : 노드 방문 체크
    # visited_dir : 노드 방문 경로 체크 ((A, B)는 A -> B 경로를 의미)
    visited = collections.defaultdict(int)
    visited_dir = collections.defaultdict(int)

    # arrows 따라 노드 좌표를 큐에 추가
    queue = collections.deque([now])
    for i in arrows:
        # 모래 시계 형태 예외를 처리하기 위해 해당 방향으로 2칸씩 추가한다.
        for _ in range(2):
            next = (now[0] + move[i][0], now[1] + move[i][1])
            queue.append(next)

            now = next

    now = queue.popleft()
    visited[now] = 1

    while queue:
        next = queue.popleft()

        # 이미 방문한 노드(visited[x]==1)인 경우
        if visited[next] == 1:
            # 해당 경로로 처음 들어온 경우인 경우 answer++
            # 처음 들어온 경우에 방이 처음 생성되므로!
            if visited_dir[(now, next)] == 0:
                answer += 1
        # 처음 방문한 노드인 경우 방문 체크를 한다.
        else:
            visited[next] = 1

        # 해당 노드로 들어온 경로를 방문 체크해준다.
        visited_dir[(now, next)] = 1
        visited_dir[(next, now)] = 1
        now = next

    return answer

프로그래머스 고득점 kit 마지막 문제, 레벨 5 치고는 생각하는 과정이 난해하지는 않다고 생각한다.

다만 한 가지 예외사항이 있는데 이것을 처리하는 발상이 절대 쉽지 않다고 생각한다.

풀이가 실패하여 어떤 분의 글을 참조하여 분석해보았다.

 

프로그래머스 > 그래프 > 방의 개수 > 파이썬(Python)

 

이 문제의 첫 번째 단계 바로 언제 방이 생성되는지 파악하는 것이다.

예시를 보면서 생각해보면 하나의 정점에 대하여 재방문할 때 방이 1개 생성되는 것을

어렵지 않게 생각할 수 있다.

 

그러나 다음과 같은 경우의 예외사항이 있다.

바로 간선을 중복하여 정점으로 돌아온 경우이다. 해당 경우는 정점을 재방문했지만 방이 생성되지 않았다.

따라서 해당 예외사항을 커버하기 위해 간선이 처음 생성되었으면서 동시에 정점을 재방문할 때 방이 생성된다고

체크하면 된다.

 

이렇게 풀면 잘 풀릴 것 만 같지만 이 문제가 레벨 5인 이유는 바로 여기에 있다.

다음과 같은 예외사항을 생각해보자.

위 상황에서는 재방문한 정점이 1개이므로 방이 1개 생성되어야 하는데 보시는 것처럼 2개가 생성된다.

그 이유는 교차점에 하나의 정점이 생기고 그 정점을 재방문하게 되어 1개의 방이 더 생성되는 것이다.

 

그러나 해당 정점은 정수단위가 아니기에 체크하려면 매우 복잡하다.

그래서 다음과 같은 아이디어가 필요하다.

위 그림과 같이 한 번에 이동할 때 2칸씩 이동하여 교차점의 정점도 하나의 정점에 자리 잡을 수 있게 한다.

그렇게 하여 모든 예외사항들을 커버할 수 있다.

 

Reference : https://pf333.tistory.com/86 

프로그래머스 > 그래프 > 방의 개수 > 파이썬(Python)