[programmers python] 49190 방의 개수

 

 

https://programmers.co.kr/learn/courses/30/lessons/49190?language=python3 

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

 

 

[문제]

원점(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

 

---

 

첫번째 시도_실패

 

다른 풀이와 질문을 참고하여 모래시계와 같은 예외의 경우 처리해줘야하는 것을 알게됨. 

위 그림의 경우, 방의 개수는 2개로 판단되어야 하는데,

 간선과 개수를 생각해본다면 방의 개수는 1개로 판단할 것이다. 이와 같은 경우의 예외를 처리하기 위해

가운에 겹치는 부분에 점이 있다고 가정한다. 

-> 이동 시 2칸씩 이동한다고 가정하면 됨

 

location = [(0, 2), (2, 2), (2, 0), (2, -2), (0, -2), (-2, -2), (-2, 0), (-2, 2)]

처음부터 2칸씩 이동한다고 가정한 후 코드 작성

 

작성해야 할 부분

1. visited: 노드 방문 여부 확인 ; 0과 1로 표현
2. visited_direction: 노드끼리 연결되어 있는지 확인; 0과 1로 표현
   • A → B와 B → A 모두 1로 설정
3. queue에 append
4. queue에 내용이 있는 경우, pop(): deque로 초기화한 경우, popleft(); next = popleft()
5. if visited == 1 && visited_direction == 0: room_count + 1 else: visited = 1로 설정
6. 노드 연결에 대해 visited_direction 양쪽 방향 모두 1로 설정; (now, next) & (next, now) = 1
7. return room_count

from collections import defaultdict, deque

def solution(arrows):
    location = [(0, 2), (2, 2), (2, 0), (2, -2), 
                (0, -2), (-2, -2), (-2, 0), (-2, 2)]
    now = (0, 0)
    
    visited = defaultdict(int)
    visited_direction = defaultdict(int)
    
    queue = deque([now])
    for arrow in arrows:
        next = (now[0] + location[arrow][0], now[1] + location[arrow][1])
        queue.append(next)
        now = next
    
    room_count = 0
    now = queue.popleft()
    visited[now] = 1
    
    while queue:
        next = queue.popleft()
        if visited[next] == 1:
            if visited_direction[(now, next)] == 0:
                room_count += 1
        else:
            visited[next] = 1
        
        visited_direction[(now, next)] = 1
        visited_direction[(next, now)] = 1
        now = next
        
    return room_count

 

 

---

 

두번째 시도 _ 성공

 

처음부터 2칸씩 초기화하는 것이 아니라, queue에 이동방향 추가해줄 때 for문 통해 2칸씩 이동하도록 설정

 

from collections import defaultdict, deque

def solution(arrows):
    location = [(0, 1), (1, 1), (1, 0), (1, -1), 
                (0, -1), (-1, -1), (-1, 0), (-1, 1)]
    now = (0, 0)
    
    visited = defaultdict(int)
    visited_direction = defaultdict(int)
    
    queue = deque([now])
    for arrow in arrows:
        for _ in range(2):
            next = (now[0] + location[arrow][0], now[1] + location[arrow][1])
            queue.append(next)
            now = next
    
    room_count = 0
    now = queue.popleft()
    visited[now] = 1
    
    while queue:
        next = queue.popleft()
        if visited[next] == 1:
            if visited_direction[(now, next)] == 0:
                room_count += 1
        else:
            visited[next] = 1
        visited_direction[(now, next)] = 1
        visited_direction[(next, now)] = 1
        now = next
        
    return room_count

 

 

---

최종 코드