백준 3108번 - 로고
3108번: 로고
로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다. 거북이는 위치와
www.acmicpc.net
로고 성공출처다국어분류
한국어
시간 제한메모리 제한제출정답맞은 사람정답 비율
| 1 초 | 128 MB | 2847 | 871 | 571 | 27.705% |
문제
로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다.
거북이는 위치와 각도로 표현할 수 있다. 거북이는 입에 연필을 물고 있는데, 연필을 내리면 움직일 때 화면에 선을 그리고, 올리면 선을 그리지 않고 그냥 지나가기만 한다.
제일 처음에 거북이는 (0,0)에 있고, 거북이가 보고 있는 방향은 y축이 증가하는 방향이다. 또한 연필은 내리고 있다.
사용자는 다음과 같은 다섯가지 명령으로 거북이를 조정할 수 있다.
- FD x: 거북이를 x만큼 앞으로 전진
- LT a: 거북이를 반시계 방향으로 a도 만큼 회전
- RT a: 거북이를 시계 방향으로 a도 만큼 회전
- PU: 연필을 올린다
- PD: 연필을 내린다.
축에 평행한 직사각형 N개가 주어졌을 때, 이 직사각형을 그리는데 필요한 PU 명령의 최솟값을 구하는 프로그램을 작성하시오.
거북이는 같은 선을 여러 번 그릴 수 있지만, 문제에 주어진 직사각형 N개를 제외한 어떤 것도 그릴 수 없다. 거북이의 크기는 아주 작아서 좌표 평면의 한 점이라고 생각하면 된다. 직사각형의 변은 축에 평행하다.
입력
첫째 줄에 직사각형의 개수 N이 주어진다. (1 ≤ N ≤ 1000)
다음 N개의 줄에는 직사각형의 좌표 x1, y1, x2, y2가 주어진다. (−500 ≤ x1 < x2 ≤ 500), (−500 ≤ y1 < y2 ≤ 500) (x1, y1)는 직사각형의 한 꼭짓점 좌표이고, (x2, y2)는 그 점의 대각선 방향의 반대 꼭짓점의 좌표이다.
출력
N개의 직사각형을 그리는 필요한 PU명령의 최솟값을 출력한다.
[ 문제 설명 ]
x1, y1 ~ x2, y2 이 주어질 때, 이 좌표가 만드는 직사각형을 1로 표시합니다.
그 와중에 x1, y1 이 되는 좌표를 큐에 넣습니다.
큐에서 x1, y1을 꺼내서 사용되는 이유는 아래와 같습니다
- 처음 가는 곳이라서 탐색을 하는 경우
- 선분이 끊어진 부분이 있으면 다시 탐색을 위해 쓰는 경우
- 다시 탐색하게 될지 안 될지 모르므로 이미 넣었지만, 방문 기록에 있어서 바로 나오는 경우
그 이후 bfs탐색을 해서 1을 찾아 따라가는 문제이지요. 다만 여기서 bfs가 끝난다는 것은.
겹쳐지지 않은 직사각형 부분이 있다는 뜻이고, 이때 +1을 해주면서 계산합니다.
그리고 다시 bfs탐색을 합니다.
( 예외 처리 )
원점에서 펜을 댄 상태로 시작하므로, 원점에 1이 있는 상황 즉 선분이 이어지는 상황일 경우, 댄 상태로 바로 이이어서 그리면 되므로 결괏값 - 1을 해주는 예외처리를 한다.
또한 곱하기 * 2를 하는 이유는 아래의 코드 블록을 첫 예제가 어떻게 돌아가는지 보게 하기 위해 넣은 부분에 넣으시고 경과를 지켜보시면 이해가 됩니다.
for i in range(500, 520):
for j in range(500, 520):
print(maps[i][j], end=" ")
print("\n")
안되실 수도 있어 첨언하자면, 저희는 자표를 그릴 때 크기가 없는 선을 그려서 1의 거리 차이도 1로 보이지만 배열로 이를 표현할 때는 1의 거리는 연결돼 있다고 판단합니다. 아래의 풀이 코드에서는요.
그렇기 때문에 * 2를 해줘서 떨어진 것을 떨이지게 끔 해주는 작업이라고 생각하시면 됩니다.
그림으로 보면 아래와 같습니다.
[ 코드 ]
from collections import deque
import sys
input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
def bfs(x, y):
q.append([x, y])
visited[x][y] = 1
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx <= 2000 and 0 <= ny <= 2000:
if maps[nx][ny] == 1 and visited[nx][ny] == 0:
visited[nx][ny] = 1
q.append([nx, ny])
n = int(input())
maps = [[0] * 2001 for _ in range(2001)]
visited = [[0] * 2001 for _ in range(2001)]
start = []
for _ in range(n):
x1, y1, x2, y2 = map(int, input().split())
x1 += 500
y1 += 500
x2 += 500
y2 += 500
x1 *= 2
y1 *= 2
x2 *= 2
y2 *= 2
start.append([x1, y1])
# 마킹하는 작업
for i in range(x1, x2 + 1):
if i == x1 or i == x2:
for j in range(y1, y2 + 1):
maps[i][j] = 1
else:
maps[i][y1] = 1
maps[i][y2] = 1
# 첫 예제로 어떻게 마킹되는 보여주기 위해 첨가한 이중 for 문
for i in range(1000, 1020):
for j in range(1000, 1020):
print(maps[i][j], end=" ")
print("\n")
q = deque()
ans = 0
for i in range(len(start)):
x, y = start[i]
if visited[x][y] == 0:
bfs(x, y)
ans += 1
if maps[1000][1000] == 1:
ans -= 1
print(ans)
후기
와!! *2 부분이 이해가 완벽히 안 됬었는데
오늘 포스팅하면서 이해가 됐습니다
아이고 좋아라~