BOJ 3108 로고

https://www.acmicpc.net/problem/3108
시간 1초, 메모리 128MB
input :

• N(1 ≤ N ≤ 1000)
• x1, y1, x2, y2가 주어진다. (−500 ≤ x1 < x2 ≤ 500), (−500 ≤ y1 < y2 ≤ 500) (x1, y1)는 직사각형의 한 꼭짓점 좌표이고, (x2, y2)는 그 점의 대각선 방향의 반대 꼭짓점의 좌표

output :

• N개의 직사각형을 그리는 필요한 PU명령의 최솟값을 출력

조건 :

• 연필을 내리면 움직일 때 화면에 선을 그리고, 올리면 선을 그리지 않고 그냥 지나가기만 한다.
• 거북이는 (0,0)에 있고, 거북이가 보고 있는 방향은 y축이 증가하는 방향이다. 또한 연필은 내리고 있다.
• FD x: 거북이를 x만큼 앞으로 전진
• LT a: 거북이를 반시계 방향으로 a도 만큼 회전
• RT a: 거북이를 시계 방향으로 a도 만큼 회전
• PU: 연필을 올린다
• PD: 연필을 내린다.

---

PU의 커맨드를 몇 번 이용하는 가에 대한 물음으로.

예제를 그려보면 어떤 직사각형들의 변이 만나는 것을 볼 수 있다. 이럴 경우엔 거북이가 계속 그림을 그리기 때문에 다른 커맨드가 필요없다.

내가 집중해야 하는 부분은 연필을 언제 올리는 지에 관한 것이다.
한 덩어리의 직사각형의 개수 만큼 연필을 들어올리는 횟수가 되기 때문에 BFS로 직사각형이 몇 개 나 있는지 확인을 해야 한다.

그런데 직사각형 사이의 거리가 1이면 이는 BFS로 탐색을 해버리기 때문에 인위적으로 거리를 더 넓혀야 한다.

그래서 입력이 가능한 범위가 -500 에서 500이기 때문에. 500을 더해 (0 <= 입력 <= 1000) 으로 만들어 주고.
거리를 2배로 늘려야 하니 2를 곱해 주자.

	x1 = 2 * (500 + item[0])
    y1 = 2 * (500 + item[1])
    x2 = 2 * (500 + item[2])
    y2 = 2 * (500 + item[3])

작은 사각형들 중에 큰 직사각형의 변에 닿지는 않고 그 안에 존재 할 가능 성도 있기 때문에, 직사각형의 내부는 비어 있어야 한다.
이를 위해. x의 좌표가 x1, x2가 아닌 경우에는 양 끝 변만 1로 바꿔준다.

    for nx in range(x1, x2 + 1):
    
        if nx == x1 or nx == x2:
            for ny in range(y1, y2 + 1):
                graph[nx][ny] = 1
                
        else:
            graph[nx][y1] = 1
            graph[nx][y2] = 1

그리고 시작하는 지점이 (0, 0)일 경우에는 펜이 이미 내려가 있기 때문에 -1 부터 시작하자.

if graph[1000][1000] == 1:
    cnt = -1
else:
    cnt = 0

정답 코드 :

import sys
from _collections import deque

n = int(sys.stdin.readline())
rectangle = []
for i in range(n):
    rectangle.append(list(map(int, sys.stdin.readline().split())))

graph = [[0] * 2001 for i in range(2001)]
position = []
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
# 0, 0 은 1000, 1000
for item in rectangle:
    x1 = 2 * (500 + item[0])
    y1 = 2 * (500 + item[1])
    x2 = 2 * (500 + item[2])
    y2 = 2 * (500 + item[3])

    position.append((x1, y1))
    for nx in range(x1, x2 + 1):
        if nx == x1 or nx == x2:
            for ny in range(y1, y2 + 1):
                graph[nx][ny] = 1
        else:
            graph[nx][y1] = 1
            graph[nx][y2] = 1


def bfs(x, y):
    q = deque([])
    q.append((x, y))
    graph[x][y] = 0

    while q:
        now_x, now_y = q.popleft()
        for i in range(4):
            nx = now_x + dx[i]
            ny = now_y + dy[i]
            if nx > 2000 or nx < 0 or ny > 2000 or ny < 0:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                q.append((nx, ny))


if graph[1000][1000] == 1:
    cnt = -1
else:
    cnt = 0
for x, y in position:
    if graph[x][y] == 1:
        cnt += 1
        bfs(x, y)

print(cnt)