프로그래머스: 방의 개수

난이도가 꽤 높은 그래프 문제이다.

방이 만들어지는 조건을 따져야 한다.

* 방이 만들어지는 조건

- 재방문한 점이다.

- 타고온 edge는 첫 방문이다.

 

여기까지는 생각하기 쉬운데, 문제는 아래와 같은 케이스다.

현재 알고리즘은 위의 그림에 대해 방을 1개로 파악한다.

이는 가운데 교차점을 정점으로 생각하지 않기 때문이다.

이 문제를 해결할 방법은 여러가지인데, 가장 간단한 방법은 하나의 화살표에 대해 이동을 2번 반복하는 것이다. 

 

def solution(arrows):
    answer = 0
    dx = (0, 1, 1, 1, 0, -1, -1, -1)
    dy = (-1, -1, 0, 1, 1, 1, 0, -1)
    
    vertex = set()
    vertex.add((0, 0))
    edge = set()
    
    cur = [0, 0]
    for arrow in arrows:
        for t in range(2):
            nxt = (cur[0]+dy[arrow], cur[1]+dx[arrow])
            e1 = (cur[0], cur[1], nxt[0], nxt[1])
            e2 = (nxt[0], nxt[1], cur[0], cur[1])
            if nxt not in vertex:
                vertex.add(nxt)
                edge.add(e1)
                edge.add(e2)
            else:
                if e1 not in edge:
                    edge.add(e1)
                    edge.add(e2)
                    answer += 1
            cur = [nxt[0], nxt[1]]
    return answer