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

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

문제 설명

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

---

 

풀이

처음 문제를 보고 그래프에 사이클이 일어나는지를 체크하여 방의 생성 여부를 확인하는 방법으로 접근하고자했다.

 

유니온-파인드 알고리즘을 이용해서 노드를 지나갈 때마다 이전 노드와 Union하는 과정을 거쳐서, 해당 노드가 이전 노드와 같은 파인드 값을 가진다면 사이클이 발생함을 의미하므로 방이 생겼다고 판단하였다.

 

이 방법은 시간 초과가 발생할 뿐더러 모래 시계 형태의 예외를 처리하지 못했다. (내가 알지 못하는 다른 예외 상황도 있었을 것이다.)

 

모래 시계 형태는 아래와 같이 노드가 없는 지점에서 대각선이 교차하는 경우를 의미하는데, 위 방법은 이와 같은 상황에서 생기는 방을 체크하지 못한다.

 

우선, 모래 시계 형태 예외를 처리하기 위해서 한 번 이동할 때 두 칸씩 이동하도록 하여, 기존에 노드가 없는 지점에도 노드가 생기도록 한다.

 

방의 생성 여부는 사이클이 생기는 것을 확인해야 함이 맞지만, 유니온-파인드 방법을 고수할 필요는 없었다. 방이 생성되는 경우는 다음과 같다.

- 방문한 노드가 이미 방문한 적이 있고,

- 해당 노드로 들어온 경로는 처음 이동한 경우

 

두 번째 조건은 한 경로를 두고 와리가리했을 경우 방이 계속해서 생김을 방지하기 위해 체크한다.

 

 

최종 코드는 다음과 같다.

# 프로그래머스 코딩테스트 연습 > 그래프 > 방의 개수

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

    # arrows 따라 노드 좌표를 큐에 추가
    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()

        # 이미 방문한 노드(visited[x]==1)인 경우
        if visited[next] == 1:
            # 해당 경로로 처음 들어온 경우인 경우 answer++
            # 처음 들어온 경우에 방이 처음 생성되므로!
            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

 

 

[참고]

프로그래머스 방의 개수 (파이썬)