Programmers | 방의 개수 - Python

soo5717·2021년 6월 30일

알고리즘 스터디

목록 보기

9/10

1. 개념 정리

1.1 그래프 (Graph)

그래프란 노드(Node)와 노드 사이에 연결 된 간선(Edge)의 정보를 가지고 있는 자료구조를 의미한다.

인접 행렬(Adjacency Materix) or 인접 리스트(Adjacency List) 방식으로 그래프를 구현할 수 있다.

	그래프	트리
방향성	방향 그래프 혹은 무방향 그래프	방향 그래프
순환성	순환 및 비순환	비순환
루트 노드 존재 여부	루트 노드가 없음	루트 노드가 존재
노드 간 관계성	부모와 자식 관계없음	부모와 자식 관계
모델의 종류	네트워크 모델	계층 모델

2. 문제 설명

2.1 방의 개수

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

스크린샷 2018-09-06 오후 4.55.33.png

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

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

2.2 제한 조건

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

2.3 입출력 예시

arrows	return
[6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0]	3

3. 풀이 과정

Level 5 문제이다! 난이도보다 구현은 쉽지만, 풀이 방식을 떠올리는 것이 어려워서 레벨이 높게 측정된 것 같다. 최대한 직접 풀어보려고 노력했지만 모래시계 관련 예외를 해결 할 수 있는 방식에 대해서 답을 찾지 못해 결국 다른 분의 풀이를 참고해서 풀었다. (참고 블로그는 하단 참고 링크에 추가해두었다)

모래시계 예외의 경우 아래 테스트 케이스를 추가해서 확인해보면 좋을 듯하다.

3.1 2칸씩 이동하기 : 성공😋

방이 생성되는 조건을 파악 후에, 조건에 해당할 때마다 answer을 증가시키는 문제이다. (이렇게 말하면 쉽지만, 실제는 조건 파악과 풀이 과정을 떠올리기가 쉽지 않다)

3.1.1 알고리즘 구현

방이 생성되는 조건은 다음 2가지의 조건을 만족할 경우이다. (이미 그려져 있던 선이 아닌지 확인해야 한다. 왔다 갔다 하는 것은 제외해야 하기 때문이다)

방문했었던 점을 다시 방문할 때 방이 하나 만들어진다.

삼각형, 사각형, 평행사변형 등 다양한 모양을 생각해보면 결국 한 점에서 모이는 것을 알 수 있다.

대각선끼리 교차할 때 방이 하나 만들어진다.

모래시계 모양을 생각하면 된다. ⌛

왼쪽 상단에서 시작한다고 생각하면 다시 왼쪽 상단에 돌아오는 것은 1번 조건에 의해서 방이 1개 생성된다.

2번 조건에 의해서 중간에 대각선이 교차할 때 즉, 이미 방문했던 중심점을 다시 방문할 때 방이 1개 더 생성된다.

그리고 여기서 핵심은 대각선이 교차하는 것을 어떻게 파악할 것인지이다. 점이 4개가 있고 그 점들을 모래시계 모양으로 연결할 경우 가운데에는 노드가 없어서 파악이 어렵다. 그럼 문제가 되는 것은 노드가 없는 것이니 노드를 만들어 주면 해결되지 않을까?

바로 한 번 이동할 때마다 2칸씩 이동하면 자연스럽게 가운데 노드가 생기게 된다!!! (누가 이런 단순하지만, 천재적인 발상을 했을까..) 어차피 문제에서 원하는 것은 그려진 그래프에서 만들어질 수 있는 방의 개수이기 때문에 스케일을 확장하는 것은 문제가 되지 않는다.

3.1.2 코드 구현

그럼 위에서 생각한 알고리즘으로 코드를 구현해보자.

(0, 0)에서부터 arrows에 지시에 따라 방향을 이동한다.

이때 한 번 이동할 때 2칸씩 이동하도록 반복을 2번 돈다.

이동한 좌표들은 queue에 저장해둔다.

queue에서 시작 좌표를 pop 한 후 방문 여부를 확인하는 visited 리스트에 방문 체크를 한다.

queue가 빌 때까지 반복문을 돌린다.

다음 좌표를 pop 한 후 방문하지 않은 좌표라면 visited에 방문 체크를 하고, 방문한 좌표이면서 이미 지나갔던 방향이 아니라면 answer을 증가시켜준다. (위의 조건 1 or 2를 충족)

양방향으로 방문 여부를 체크해준다.

answer을 반환해준다.

방문 노드와 방문한 간선을 체크할 때 defaultdict(사전의 초깃값을 주어진 객체의 기본값으로 지정 가능)를 활용하면 편리하게 구현할 수 있다.

전체 코드 (Python)

from collections import defaultdict, deque

def solution(arrows):
    move = [(-1, 0), (-1, 1), (0, 1), (1, 1), 
            (1, 0), (1, -1), (0, -1), (-1, -1)]
    now = (0, 0) # x(열), y(행)
    
    visited = defaultdict(int)
    visited_dir = defaultdict(int) # (A, B)는 A -> B
    
    queue = deque([now])
    for arrow in arrows: # arrows 방향 이동
        for _ in range(2): # 모래시계 예외 처리를 위함
            next = (now[0] + move[arrow][0], now[1] + move[arrow][1])
            queue.append(next)
            now = next
            
    answer = 0
    now = queue.popleft()
    visited[now] = 1 # 방문 체크
    
    while queue:
        next = queue.popleft()
        
        if visited[next] == 1: # 조건 1 or 2 해당
            if visited_dir[(now, next)] == 0:
                answer += 1
        else:
            visited[next] = 1
        
        # 왔다 갔다 방지하기 위함
        visited_dir[(now, next)] = 1
        visited_dir[(next, now)] = 1
        now = next

    return answer

실행 결과

4. 핵심 정리

4.1 🔥 최종 풀이 🔥

from collections import defaultdict, deque

def solution(arrows):
    move = [(-1, 0), (-1, 1), (0, 1), (1, 1), 
            (1, 0), (1, -1), (0, -1), (-1, -1)]
    now = (0, 0) # x(열), y(행)
    
    visited = defaultdict(int)
    visited_dir = defaultdict(int) # (A, B)는 A -> B
    
    queue = deque([now])
    for arrow in arrows:
        for _ in range(2): # 모래시계 예외 처리를 위함
            next = (now[0] + move[arrow][0], now[1] + move[arrow][1])
            queue.append(next)
            now = next
            
    answer = 0
    now = queue.popleft()
    visited[now] = 1
    
    while queue:
        next = queue.popleft()
        
        if visited[next] == 1:
            if visited_dir[(now, next)] == 0:
                answer += 1
        else:
            visited[next] = 1
        
        visited_dir[(now, next)] = 1
        visited_dir[(next, now)] = 1
        now = next

    return answer