[프로그래머스] 방의 개수 / 그래프 / python

문제

https://school.programmers.co.kr/learn/courses/30/lessons/49190

프로그래머스

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

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

그림을 그릴 때, 사방이 막히면 방하나로 샙니다.

이동하는 방향이 담긴 배열 arrows가 매개변수로 주어질 때, 방의 갯수를 return 하도록 solution 함수를 작성하세요.

제한사항

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

풀이

아이디어

먼저, 어떻게 하면 방이 생기는지 정의해본다

출발한 정점에 대해 다시 돌아온경우, 재방문 할 때 방이 하나 생긴다

그래프 관점으로 봤을때 사이클이 형성된 경우이다

 

하지만 예외가 있다

정점을 다시 돌아왔지만(사이클이 형성 되었지만) 방문한 간선을 통해 돌아오면 방이 생기지 않는다

그렇다면 조건이 하나더 추가된다

 

정점을 재방문 하고, 간선이 처음 생성된 경우(방문하지 않은 간선을 통해 돌아옴)

하지만.. 또 하나의 예외가 존재하게 된다

위의 조건으로 보면, 재방문하게된 정점이 생기면 방이 1개 생긴다

 

재방문한 점이 1개이지만 방이 2개가 생기는 모래시계형이 예외가 된다

교차점에서 새로운 정점이 생성되고 이를 재방문 하게 되기 때문이다

 

교차점이 생기는 곳의 좌표는 정수로 표현이 안되기 때문에 계산이 복잡해진다

이를 해결하기 위해 이동거리를 2로 만들어준다

그럼 교차점을 새로운 정점으로 생각하여 재방문한 정점으로 계산 할 수 있음!

 

8방향으로 움직이는 좌표계를 설정하고 두칸씩 움직이면서 사이클이 형성되었는지, 방문하지 않은 간선을 이용했는지 확인하면서 끝까지 움직이면 된다

코드

def solution(arrows):
    #    위 북동 오른 남동 아래 남서 왼 북서 
    dx = [0, 1, 1, 1, 0, -1, -1, -1]
    dy = [-1, -1, 0, 1, 1, 1, 0, -1]

    x, y = 0, 0
    # 중복을 없애기 위해 set으로 설정
    visited_node = set()
    visited_node.add((x,y))
    route = set()
    cycle = 0
    for arrow in arrows:
        # 모래시계 교차점을 정점으로 만들기 위해 두칸 이동
        for _ in range(2):
            nx, ny = x+dx[arrow], y + dy[arrow]
            if (nx,ny) in visited_node and (x, y, nx, ny) not in route:
                cycle += 1
            # 엣지 추가 (왔다갔다 경로를 이용)
            route.add((x,y, nx, ny))
            route.add((nx, ny, x,y))
            # 노드 추가
            visited_node.add((nx, ny))
            x, y = nx, ny
    return cycle

 

오일러공식

알고리즘을 꽤 오래 안하다가 다시 하니 까먹는게 정말 많다

다른 사람의 풀이를 통해 알게된 오일러공식을 이용한 풀이

v(꼭짓점의 개수) - e(변의 개수) + f(면의 개수) = 2

한쪽 방향으로 쭉 긋게 되면 v-e = 1이된다.

사방이 막혀야 방으로 인정되기때문에 식에 포함된 바깥 평면은 방이되지 못하므로 1을 빼줘야한다.

solution(arrows):
    answer = 0
    d = {0 : (-1, 0), 1 : (-1, 1), 2 : (0, 1), 3 : (1, 1), 4 : (1, 0), 5 : (1, -1), 6 : (0, -1), 7 : (-1, -1)}
    x = (0, 0)
    v = set({x})
    e = set()

    for arrow in arrows:
        for i in range(2):
            y = (x[0] + d[arrow][0], x[1] + d[arrow][1])
            v.add(y)
            e.add((x[0] + y[0], x[1] + y[1]))
            x = y
        
    answer = len(e) - len(v) + 1
        
    return answer

print(solution([6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0]))

방의 개수 = 1 - v +e

 

 

참고

https://sangsangss.tistory.com/186