[Python] 방의 개수

1. 문제

 

 

 

2. 풀이 과정

방법 1) arrows를 하나씩 보면서 그 때마다 면이 생기면 count를 했다.

 

면이 생기는 경우는 크게 두 경우로 나눠볼 수 있다.

1. 이미 지나간 점(vertex)를 또 지나가는 경우

2. 다른 점으로 이동하면서 간선들 간에 교점이 생기는 경우

두 경우는 동시에 발생할 수도 있어서 if를 두 번 사용하여 계산하였다.

 

여기서 주의해야 할 점은 이미 지나간 간선을 다시 지나가면서 중복 count되지 않도록 해야 한다.

코드에서는 지금 지나가는 간선이 edg에 있는지 확인하는 걸로 중복되지 않도록 했다.

def solution(arrows):
    answer = 0
    dxy = [(0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)]
    ver = set()
    edg = set()
    
    x, y = 0, 0
    ver.add((x, y))
    for a in arrows:
        nx, ny = x + dxy[a][0], y + dxy[a][1]
        
        edge = ((x, y), (nx, ny))
        if (x, y) > (nx, ny):
            edge = ((nx, ny), (x, y))
        
        if edge not in edg: #edge가 겹치지 않을 때
            # case1) vertex가 겹침
            if (nx, ny) in ver:
                answer += 1
            # case2) edge가 겹침 (교차선)
            if a%2 == 1 :
                e = ((nx, y), (x, ny)) #교차되는 선
                if (nx, y) > (x, ny):
                    e = ((x, ny), (nx, y))
                if e in edg: #교차선이 존재하면
                    answer += 1
        
        edg.add(edge)
        ver.add((nx, ny))
        x, y = nx, ny
    
    return answer

 

방법 2) 오일러 공식 이용

 

오일러 공식 : V - E + F = 2

*V = vertex(정점)의 수

*E = edge(간선)의 수

*F = 면의 수

 

증명 과정은 아래 주소의 블로그를 참고하였다.

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=skh8464&logNo=221038912166

 

오일러 공식은 교점을 기준으로 간선을 count했을 때 성립이 된다. 지금 문제에서는 vertex에서만 교차되는 것이 아니라 edge들끼리도 교차될 수 있다. vertex가 교차되는 경우는 edge의 끝부분에서 교차되지만 edge들 간에 교차될 경우 edge 중간에서 교차된다. 따라서 이때는 교점이 중간 지점에 있기 때문에, edge의 길이를 1/2가 기준이 되어야 한다.

 

 

대각선의 경우 길이를 1을 기준으로, 다른 선들은 길이를 2를 기준으로 하였다. 실제로 더 작은 1에 맞추어 다른 선들의 길이도 작게 맞춰 주어도 되지만, 교점이 생길 일이 없으니 필요 없는 연산은 생략해준 것이다.

어차피 반으로 자르면 edge도 하나 증가하고 vertex도 하나 증가해서 연산 결과는 같기 때문에 생략해도 성립한다.

 

마지막에 1을 빼는 이유는 오일러 공식에서는 도형의 바깥의 면 1개도 포함해서 계산하는 공식이기 때문에, 바깥 면을 count하지 않는 이 문제에서는 결과에서 1을 빼주어야 한다.

def edge(e1, e2): #방향이 다른 edge를 같은 edge로 고려하기 위함
    if e1 > e2:
        return (e2, e1)
    return (e1, e2)

def solution(arrows):
    dxy = [(0, 2), (2, 2), (2, 0), (2, -2), (0, -2), (-2, -2), (-2, 0), (-2, 2)]
    ver = set()
    edg = set()
    
    xy = (0, 0)
    ver.add(xy)
    for a in arrows:
        nxy = (xy[0] + dxy[a][0], xy[1] + dxy[a][1])
        
        if a%2 == 1: #대각선인 경우
            mxy = (xy[0] + dxy[a][0]//2, xy[1] + dxy[a][1]//2)
            ver.add(mxy)
            edg.add(edge(xy, mxy))
            edg.add(edge(mxy, nxy))
        else:
            edg.add(edge(xy, nxy))

        ver.add(nxy)
        xy = nxy
    
    return (2-len(ver)+len(edg)-1) #오일러 공식