좌표 2배로 관리하기

문제

프로그래머스

 

프로그래머스

---

 

재정의

아이템 줍기 문제이다.

사각형이 겹친 형태로 있을 때, 가장 외곽라인들의 총합을 길로 정한다.

이 길에서 최단거리로 목표지점 까지 도달하는 방법을 구하는 문제.

 

최단거리이고 가중치가 다 동일하므로, BFS로 최단 거리를 구할 수 있다.

겹친 사각형에서 어떻게 루트를 구할 것인가가 관건인 문제.

 

---

 

사각형의 내부를 채우면서 판별하기

 

먼저 사각형의 내부를 0으로 채운다.

그리고 테투리를 그리는데, 이 때 값이 0이 아닐 때만 그리는 방법이다.

Simple하고 효율이 좋다.

for r in rectangle:
    	# 모든 좌표값 2배
        x1, y1, x2, y2 = map(lambda x: x*2, r)
        for i in range(x1, x2+1):
            for j in range(y1, y2+1):
                if x1 < i < x2 and y1 < j < y2:
                    field[i][j] = 0
                # 다른 직사각형의 내부가 아니면서 현재 직사각형의 테두리일 때 1로 채움
                elif field[i][j] != 0:
                    field[i][j] = 1

 

---

 

사각형을 전부 그리고, DFS로 라인 따기

 

일단 무작정 그림을 다 그린다.

그리고 바깥영역에서 DFS를 해서 충돌하는 라인을 딴다.

모서리 때문에 8방향으로 탐색해야 함에 유의할 것.

def get_outline(field:List[List[bool]]) -> List[List[bool]]:
    visit = [[0] * 102 for _ in range(102)]
    new_field = [[0] * 102 for _ in range(102)]
    
    stack = [(0, 0)]
    visit[0][0] = 1
    
    while stack:
        x, y = stack.pop()
        
        if field[y][x]:
            new_field[y][x] = 1
            continue
        
        for dx, dy in zip(DX, DY):
            new_x = x + dx
            new_y = y + dy
            
            if not(0<=new_x<=101)\
                    or not(0<=new_y<=101)\
                    or visit[new_y][new_x]:
                continue
            
            visit[new_y][new_x] = 1
            stack.append((new_x, new_y))
    
    return new_field

 

---

 

발생하는 문제점

 

우리는 데이터를 2차원 배열로 다룬다.

그렇게 되면 좌표 한 칸의 의미는 다른 좌표와의 연결을 의미한다.

0과 1의 연결, 1과 2의 연결인 경우에는 값이 인접해 있기 때문에, 라인을 딸 수가 없다.

 

그래서 좌표를 2배로 해서 저장을 하게 되면, 인접하는 문제가 사라진다.

그리고 결과에서 나누기 2를 하면 값을 똑같이 얻을 수 있다.

 

방의 개수 문제

 

대각선의 교점이 0.5 소수점에 발생할 수 있다.

정수의 배열이기 때문에 0.5를 다룰 수 없기 때문에 *2를 이용하여

정수로 관리할 수 있다. 해당 문제는 길이가 아닌 판별문제이므로 되돌릴 필요가 없다.

 

---

 

피드백

좌표계를 배수하는 방법으로 2차원 좌표계의 충돌을 막을 수 있다.

배수를 하는 방법으로 소수점 문제를 예방할 수 있다.

 

방의 개수 문제에서는 오일러 문제의 일종이라 심플하게 구할 수 있다.

특정 좌표에 재 방문을 하면 1개의 사이클이 발생했다고 할 수 있다.

 

다만, 반복적인 경로를 예방해야 하므로,

어디서 와서 재방문을 했는지 확인을 해야 한다.