[프로그래머스/Python] 방의 개수 - Level5

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

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

이 문제는 Level5 답게 굉장히 어려웠다.. 그래서 어떻게 방의 개수를 셀 수 있는지 전혀 생각나지 않았다... 그래서 문제를 풀지는 못하고 다른 사람의 풀이를 보고 정리를 했다.

 

방의 개수를 어떻게 구할 수 있는지에 대한 것은 이 링크를 참고하면 좋을 것 같다. 굉장히 상세하게 정리해주셔서 도움이 많이 되었다.

결론만 말하자면, 방이 생성되려면 "방문한 노드가 이미 방문한 적 있으며 해당 노드로 들어온 경로는 처음인 경우" 이다. 하지만 다음 그림처럼 모래시계 형태(대각선이 교차)는 방이 생성될 수 없다. 따라서 모래시계 형태가 생기는 것을 막기 위해  한 번 이동할 때 두 칸씩 이동하도록 하여 기존에 노드가 없는 지점에도 노드가 생기도록 한다.

 

 

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 = collections.defaultdict(int) # 노드 방문 체크
    visited_dir = collections.defaultdict(int) # 노드 방문 경로 체크, (A,B)는 A -> B 경로를 의미

    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() # 다음 노드

        if visited[next] == 1: # 이미 방문한 노드일 경우
            if visited_dir[(now, next)] == 0: # 해당 경로로 처음 들어온 경우
                answer += 1 # 방이 생성되므로 answer에 +1
        else: # 방문한 노드가 아닐 경우 방문 처리
            visited[next] = 1

        # 해당 노드로 들어온 경로를 방문 처리
        visited_dir[(now, next)] = 1
        visited_dir[(next, now)] = 1
        now = next

    return answer

1. 방문할 노드들을 저장할 큐를 생성한다. 시작 노드(now)는 미리 넣어둔다.

2. arrows 를 돌면서 방문할 노드들을 큐에 저장한다. 이 때 모래 시계 형태를 막기 위해 해당 방향으로 2칸씩 추가한다.

3. 현재 노드이며 시작 노드를 now에 저장하고 시작 노드는 방문 처리를 한다.

4. 방의 개수를 센다.

    4-1. 다음 노드를 가져와 next에 저장한다.

    4-2. next가 이미 방문한 노드이며 해당 경로로 처음 들어온 경우 방이 생성되므로 answer에 +1 한다.

    4-3. next가 방문한 노드가 아닌 경우 방문 처리를 한다.

    4-4. 해당 노드로 들어온 경로를 방문 처리한다.