문제

로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다.

거북이는 위치와 각도로 표현할 수 있다. 거북이는 입에 연필을 물고 있는데, 연필을 내리면 움직일 때 화면에 선을 그리고, 올리면 선을 그리지 않고 그냥 지나가기만 한다.

제일 처음에 거북이는 (0,0)에 있고, 거북이가 보고 있는 방향은 y축이 증가하는 방향이다. 또한 연필은 내리고 있다.

사용자는 다음과 같은 다섯가지 명령으로 거북이를 조정할 수 있다.

  1. FD x: 거북이를 x만큼 앞으로 전진
  2. LT a: 거북이를 반시계 방향으로 a도 만큼 회전
  3. RT a: 거북이를 시계 방향으로 a도 만큼 회전
  4. PU: 연필을 올린다
  5. PD: 연필을 내린다.

축에 평행한 직사각형 N개가 주어졌을 때, 이 직사각형을 그리는데 필요한 PU 명령의 최솟값을 구하는 프로그램을 작성하시오.

거북이는 같은 선을 여러 번 그릴 수 있지만, 문제에 주어진 직사각형 N개를 제외한 어떤 것도 그릴 수 없다. 거북이의 크기는 아주 작아서 좌표 평면의 한 점이라고 생각하면 된다. 직사각형의 변은 축에 평행하다.

www.acmicpc.net/problem/3108

  • 입력

첫째 줄에 직사각형의 개수 N이 주어진다. (1 ≤ N ≤ 1000)

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

  • 출력

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

최종 코드

처음에 두 가지를 놓쳤다.

  1. 2차원 배열을 사용해서 실제로 연결되지 않는 길로 갈 수 있게 했다. -> 인접리스트를 사용해야 한다.
  2. 직사각형이 시작점을 포함하는 경우를 고려하지 않았다. -> 이 경우 연필을 올릴 필요가 없으므로 count하지 않는다.

위 두 가지를 고려하여 짠 코드이다.

import sys
from collections import deque

def cal(a):
    return int(a) + 500

def bfs(sx, sy):
    global cnt
    q = deque()
    q.append([sx, sy])
    visit[sx][sy] = True
    while q:
        x, y = q.popleft()
        for nx, ny in g[x][y]:
            if visit[nx][ny] == False:
                # 직사각형이 시작점을 포함하는 경우 -1
                if nx == 500 and ny == 500:
                    cnt -= 1
                visit[nx][ny] = True
                q.append([nx, ny])

n = int(sys.stdin.readline())
g = [[[] for _ in range(1001)] for _ in range(1001)]
visit = [[False]*1001 for _ in range(1001)]
start = []
# 인접리스트 생성
for _ in range(n):
    x1, y1, x2, y2 = map(cal, sys.stdin.readline().split())
    start.append([x1, y1, x2, y2])
    # 직사각형의 세로
    for i in range(x1+1, x2+1):
        g[i][y1].append([i - 1, y1])
        g[i - 1][y1].append([i, y1])
        g[i][y2].append([i - 1, y2])
        g[i - 1][y2].append([i, y2])
    # 직사각형의 가로
    for i in range(y1+1, y2+1):
        g[x1][i].append([x1, i - 1])
        g[x1][i - 1].append([x1, i])
        g[x2][i].append([x2, i - 1])
        g[x2][i - 1].append([x2, i])

cnt = 0
for x1, y1, x2, y2 in start:
    if visit[x1][y2] == False:
        cnt += 1
        bfs(x1, y1)
print(cnt)

Enhanced

찾아보니 인접리스트가 아닌 2차원 배열을 사용해서 푸는 방법이 있었다!

앞서 2차원 배열을 사용하면 점 간의 연결 여부를 파악할 수 없다고 했는데, 공간을 2배로 늘려주어 이 문제를 해결할 수 있었다. 공간을 2배로 늘려주면 원래 연결된 직사각형 끼리는 그대로 선으로 연결되고, 연결되지 않은 직사각형과는 사이에 공간이 생겨서 연결 여부를 확실히 알 수 있다.

이런 방법은 어떻게 생각해내는 건지.. 오늘도 하나 배웠다! 이 방법을 사용하니까 시간이 반으로 줄었다.

import sys
from collections import deque

# 좌표를 양수로 만들기 위해 500을 더하고, 연결 여부를 확인하기 위해 2를 곱한다
def cal(a):
    return (int(a) + 500) * 2

def bfs(sx, sy):
    global cnt
    q = deque()
    q.append([sx, sy])
    visit[sx][sy] = True
    while q:
        x, y = q.popleft()
        for dx, dy in zip([0, 0, -1, 1], [-1, 1, 0, 0]):
            nx = x + dx
            ny = y + dy
            if 0 <= nx < 2001 and 0 <= ny < 2001 and visit[nx][ny] == 0:
                # 직사각형이 시작점을 포함하는 경우 -1
                if nx == 1000 and ny == 1000:
                    cnt -= 1
                visit[nx][ny] = 1
                q.append([nx, ny])

n = int(sys.stdin.readline())
visit = [[-1]*2001 for _ in range(2001)]
start = []
for _ in range(n):
    x1, y1, x2, y2 = map(cal, sys.stdin.readline().split())
    start.append([x1, y1])
    # 직사각형의 세로 체크
    for i in range(x1, x2+1):
        visit[i][y1] = 0
        visit[i][y2] = 0
    # 직사각형의 가로 체크
    for i in range(y1, y2+1):
        visit[x1][i] = 0
        visit[x2][i] = 0

cnt = 0
for x1, y1 in start:
    if visit[x1][y1] == 0:
        cnt += 1
        bfs(x1, y1)
print(cnt)

참고 사이트