[프로그래머스] 방의 개수(미완성)

문제 이해하기

이동하는 방향이 담긴 배열이 주어질 때, 방의 갯수를 return하는 문제였습니다.

 

문제 해결 방법 설명하기

1. 닫친 방이란?

닫친 방을 생각해본다면 이미 방문한 정점에 다시 한번 방문 했을 때 닫친 방이라고 생각할 수 있다.하지만 주의할 점은 다시 방문한 정점은 이전에 사용되지 않은 edge로 부터 진입해야 한다는 점이다.

 

2. 배열의 확장 

배열의 확장은 왜 필요한가.

4각형 배열이기 때문에 중간 정점은 생각하지 못하게 된다.

따라서 배열의 확장을 통해 중간 정점을 표현할 수 있게 만들어줘야 닫친 방을 모두 찾을 수 있게 된다.

 

코드

from collections import deque
def solution(arrows):
    answer = 0
    visited = {}
    dir = {}

    dir[0] = [-1, 0]
    dir[1] = [-1, 1]
    dir[2] = [0, 1]
    dir[3] = [1, 1]
    dir[4] = [1, 0]
    dir[5] = [1, -1]
    dir[6] = [0, -1]
    dir[7] = [-1, -1]
    
    start_x = 0
    start_y = 0
    
    visited[(start_x, start_y)] = True 
    visited_edge = {} 
    
    for i in range(len(arrows)):
        for j in range(2):
            next_x = start_x + dir[arrows[i]][0]
            next_y = start_y + dir[arrows[i]][1]
            
            if (next_x, next_y) in visited and not (start_x, start_y, next_x, next_y) in visited_edge:
                answer += 1
                    
            
            visited_edge[(start_x, start_y, next_x, next_y)] = True
            visited_edge[(next_x, next_y, start_x, start_y)] = True
            visited[(next_x, next_y)] = True  
            
            start_x = next_x
            start_y = next_y
    
    return answer

if __name__ == "__main__":
    arrows = [6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0]
    print(solution(arrows))  # 3

코드 리뷰

 

배운점 정리하기

저는 닫친 방이란 node와 edeg가 같으면 닫친방이라고 생각했습니다.하지만 생각해보니 visited가 여러 번인 닫친 배열은 node와 edeg가 달라질 수 밖에 없었고 해결할 수 없었다.