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

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

728x90

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. 해당 노드로 들어온 경로를 방문 처리한다.

728x90

from http://soohyun6879.tistory.com/187 by ccl(A) rewrite - 2021-08-10 11:26:11