그래프 - 방의 개수

1. 문제

문제 설명

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

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

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

제한사항

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

입출력 예

입출력 예 설명

2. 풀이 과정

그래프

주어진 경로를 도는 과정에서, 방이 생성되는 필요충분조건은 다음과 같다.

1) 이미 방문 한 점을 방문했을 때
2) 그 점을 방문할 때 처음 가는 경로로 방문했을 때

위의 두 가지 조건을 만족하면 방이 생성되며, 이 두 가지 조건 중 하나라도 만족하지 못하면 방이 새로 생성되지 않음을 알 수 있다. 첫 번째 조건을 만족하지 못하면 방이 생기지 않으며, 두 번째 조건을 만족하지 못하면 이미 카운트한 방을 중복 카운트 하게 된다.
여기서 주의할 점은, 실제로 문제를 풀다 보면 주어진 격자 안에 있는 점을 거치지 않고도 방이 생성될 수 있다. 예를 들어, (0,0) -> (1,1) -> (0,1) -> (1,0) 과 의 경로를 거치게 되면 (0.5,0.5)를 지날 때 방이 1개 생성되게 된다. 이러한 경우를 모두 카운트하기 위해, 입력이 주어지면 화살표 방향으로 2만큼 이동하는 것으로 문제를 변형할 수 있다. 그렇게 되면 위의 경우에 방은 (0,0) -> (2,2) -> (0,2) -> (2,0)의 경로에서 (1,1)을 지날 때 생성된다.

코드

import collections

def solution(arrows):
    answer = 0
    directions = ((0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1),(-1,0),(-1,1))
    
    ## 위치와 경로에 대한 방문 체크, 중간에 없는 key를 조회하는 것을 고려하여 defaultdict 이용
    location_visit = collections.defaultdict(int)
    path_visit = collections.defaultdict(int)
    location_history = []
    depart = (0,0)
    location_history += [depart]
    
    for arrow in arrows:
        for _ in range(2): ## 해당 좌표를 거치지 않았지만 방이 생기는 경우를 고려하여 같은 경로를 2번에 걸쳐서 가도록 만듬
            arrive = (depart[0]+directions[arrow][0], depart[1]+directions[arrow][1])
            location_history += [arrive]
            depart = arrive
    
    location_visit[(0,0)] = 1
    for i in range(1,len(location_history)):
        depart = location_history[i-1]
        arrive = location_history[i]
        if location_visit[arrive] == 1: ## 이미 방문한 좌표인 경우
            if path_visit[(depart,arrive)] == 0: ## 처음 오는 경로인 경우: 방이 1개 생긴 것과 동치
                answer += 1
        else:
            location_visit[arrive] = 1 ## 방문 표시
        path_visit[(depart,arrive)] = 1
        path_visit[(arrive,depart)] = 1 ## 동일한 경로를 거꾸로 갔을 경우를 고려하기 위해
                
    return answer

출처: 프로그래머스 코딩테스트 연습, 그래프, 가장 먼 노드 (https://programmers.co.kr/learn/courses/30/lessons/49190)