문제
로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다.
거북이는 위치와 각도로 표현할 수 있다. 거북이는 입에 연필을 물고 있는데, 연필을 내리면 움직일 때 화면에 선을 그리고, 올리면 선을 그리지 않고 그냥 지나가기만 한다.
제일 처음에 거북이는 (0,0)에 있고, 거북이가 보고 있는 방향은 y축이 증가하는 방향이다. 또한 연필은 내리고 있다.
사용자는 다음과 같은 다섯가지 명령으로 거북이를 조정할 수 있다.
- FD x: 거북이를 x만큼 앞으로 전진
- LT a: 거북이를 반시계 방향으로 a도 만큼 회전
- RT a: 거북이를 시계 방향으로 a도 만큼 회전
- PU: 연필을 올린다
- PD: 연필을 내린다.
축에 평행한 직사각형 N개가 주어졌을 때, 이 직사각형을 그리는데 필요한 PU 명령의 최솟값을 구하는 프로그램을 작성하시오.
거북이는 같은 선을 여러 번 그릴 수 있지만, 문제에 주어진 직사각형 N개를 제외한 어떤 것도 그릴 수 없다. 거북이의 크기는 아주 작아서 좌표 평면의 한 점이라고 생각하면 된다. 직사각형의 변은 축에 평행하다.
출력
N개의 직사각형을 그리는 필요한 PU명령의 최솟값을 출력한다.
W3sicHJvYmxlbV9pZCI6IjMxMDgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI4NWNcdWFjZTAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yjg1Y1x1YWNlMFx1YjI5NCBcdWM4ZmNcdWI4NWMgXHVhZDUwXHVjNzIxXHVjNmE5XHVjNWQwIFx1YzRmMFx1Yzc3NFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3OThcdWJjMGQgXHVjNWI4XHVjNWI0XHVjNzc0XHViMmU0LiBcdWI4NWNcdWFjZTBcdWM3NTggXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWQyYjlcdWM5ZDVcdWM3NDAgXHVhYzcwXHViZDgxXHVjNzc0IFx1Yjg1Y1x1YmQwN1x1Yzc3OFx1YjM3MCwgXHVjMGFjXHVjNmE5XHVjNzkwXHViMjk0IFx1Yzc3NCBcdWFjNzBcdWJkODFcdWM3NzQgXHViODVjXHViZDA3XHVjNzQ0IFx1YzZjMFx1YzljMVx1Yzc3NFx1YjI5NCBcdWJhODVcdWI4MzlcdWM3NDQgXHVjNzg1XHViODI1XHVkNTc0IFx1ZDY1NFx1YmE3NFx1YzVkMCBcdWIzYzRcdWQ2MTVcdWM3NDQgXHVhZGY4XHViOWI0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWM3MFx1YmQ4MVx1Yzc3NFx1YjI5NCBcdWM3MDRcdWNlNThcdWM2NDAgXHVhYzAxXHViM2M0XHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFjNzBcdWJkODFcdWM3NzRcdWIyOTQgXHVjNzg1XHVjNWQwIFx1YzVmMFx1ZDU0NFx1Yzc0NCBcdWJiM2NcdWFjZTAgXHVjNzg4XHViMjk0XHViMzcwLCBcdWM1ZjBcdWQ1NDRcdWM3NDQgXHViMGI0XHViOWFjXHViYTc0IFx1YzZjMFx1YzljMVx1Yzc3YyBcdWI1NGMgXHVkNjU0XHViYTc0XHVjNWQwIFx1YzEyMFx1Yzc0NCBcdWFkZjhcdWI5YWNcdWFjZTAsIFx1YzYyY1x1YjlhY1x1YmE3NCBcdWMxMjBcdWM3NDQgXHVhZGY4XHViOWFjXHVjOWMwIFx1YzU0YVx1YWNlMCBcdWFkZjhcdWIwZTUgXHVjOWMwXHViMDk4XHVhYzAwXHVhZTMwXHViOWNjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODFjXHVjNzdjIFx1Y2M5OFx1Yzc0Y1x1YzVkMCBcdWFjNzBcdWJkODFcdWM3NzRcdWIyOTQgKDAsMClcdWM1ZDAgXHVjNzg4XHVhY2UwLCBcdWFjNzBcdWJkODFcdWM3NzRcdWFjMDAgXHViY2Y0XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWQ1YTVcdWM3NDAgeVx1Y2Q5NVx1Yzc3NCBcdWM5OWRcdWFjMDBcdWQ1NThcdWIyOTQgXHViYzI5XHVkNWE1XHVjNzc0XHViMmU0LiBcdWI2MTBcdWQ1NWMgXHVjNWYwXHVkNTQ0XHVjNzQwIFx1YjBiNFx1YjlhY1x1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBhY1x1YzZhOVx1Yzc5MFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YjJlNFx1YzEyZlx1YWMwMFx1YzljMCBcdWJhODVcdWI4MzlcdWM3M2NcdWI4NWMgXHVhYzcwXHViZDgxXHVjNzc0XHViOTdjIFx1Yzg3MFx1YzgxNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPkZEIHg6IFx1YWM3MFx1YmQ4MVx1Yzc3NFx1Yjk3YyB4XHViOWNjXHVkMDdjIFx1YzU1ZVx1YzczY1x1Yjg1YyBcdWM4MDRcdWM5YzQ8XC9saT5cclxuXHQ8bGk+TFQgYTogXHVhYzcwXHViZDgxXHVjNzc0XHViOTdjIFx1YmMxOFx1YzJkY1x1YWNjNCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgYVx1YjNjNCBcdWI5Y2NcdWQwN2MgXHVkNjhjXHVjODA0PFwvbGk+XHJcblx0PGxpPlJUIGE6IFx1YWM3MFx1YmQ4MVx1Yzc3NFx1Yjk3YyBcdWMyZGNcdWFjYzQgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIGFcdWIzYzQgXHViOWNjXHVkMDdjIFx1ZDY4Y1x1YzgwNDxcL2xpPlxyXG5cdDxsaT5QVTogXHVjNWYwXHVkNTQ0XHVjNzQ0IFx1YzYyY1x1YjliMFx1YjJlNDxcL2xpPlxyXG5cdDxsaT5QRDogXHVjNWYwXHVkNTQ0XHVjNzQ0IFx1YjBiNFx1YjliMFx1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWNkOTVcdWM1ZDAgXHVkM2M5XHVkNTg5XHVkNTVjIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBOXHVhYzFjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVhZGY4XHViOWFjXHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBQVSBcdWJhODVcdWI4MzlcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWFjNzBcdWJkODFcdWM3NzRcdWIyOTQgXHVhYzE5XHVjNzQwIFx1YzEyMFx1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YWRmOFx1YjliNCBcdWMyMTggXHVjNzg4XHVjOWMwXHViOWNjLCBcdWJiMzhcdWM4MWNcdWM1ZDAgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBOXHVhYzFjXHViOTdjIFx1YzgxY1x1YzY3OFx1ZDU1YyBcdWM1YjRcdWI1YTQgXHVhYzgzXHViM2M0IFx1YWRmOFx1YjliNCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWFjNzBcdWJkODFcdWM3NzRcdWM3NTggXHVkMDZjXHVhZTMwXHViMjk0IFx1YzU0NFx1YzhmYyBcdWM3OTFcdWM1NDRcdWMxMWMgXHVjODhjXHVkNDVjIFx1ZDNjOVx1YmE3NFx1Yzc1OCBcdWQ1NWMgXHVjODEwXHVjNzc0XHViNzdjXHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWJjYzBcdWM3NDAgXHVjZDk1XHVjNWQwIFx1ZDNjOVx1ZDU4OVx1ZDU1OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWM4OGNcdWQ0NWMgeDEsIHkxLCB4MiwgeTJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoJm1pbnVzOzUwMCAmbGU7IHgxICZsdDsgeDIgJmxlOyA1MDApLCAoJm1pbnVzOzUwMCAmbGU7IHkxICZsdDsgeTIgJmxlOyA1MDApICh4MSwgeTEpXHViMjk0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWQ1NWMgXHVhZjJkXHVjOWQzXHVjODEwIFx1Yzg4Y1x1ZDQ1Y1x1Yzc3NFx1YWNlMCwgKHgyLCB5MilcdWIyOTQgXHVhZGY4IFx1YzgxMFx1Yzc1OCBcdWIzMDBcdWFjMDFcdWMxMjAgXHViYzI5XHVkNWE1XHVjNzU4IFx1YmMxOFx1YjMwMCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NTggXHVjODhjXHVkNDVjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk5cdWFjMWNcdWM3NTggXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YWRmOFx1YjlhY1x1YjI5NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgUFVcdWJhODVcdWI4MzlcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMTA4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTE9HTyIsImRlc2NyaXB0aW9uIjoiPHA+Q29tcGV0aXRpb24gdGFza3MgZm9yIHRoZSBwcm9ncmFtbWluZyBsYW5ndWFnZSBMT0dPIG9mdGVuIGludm9sdmUgZHJhd2luZyByZWN0YW5nbGVzIG9uIHRoZSBzY3JlZW4uIERyYXdpbmcgaW4gTE9HTyBpcyBkb25lIGJ5IG1vdmluZyBhIHR1cnRsZS1zaGFwZWQgY3Vyc29yLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgdHVydGxlIGlzIGRlZmluZWQgYnkgaXRzIHBvc2l0aW9uIGFuZCBhbmdsZS4gSXQgaG9sZHMgaW4gaXRzIG1vdXRoIGEgcGVuY2lsIHRoYXQgY2FuIGJlIHJhaXNlZCBvciBsb3dlcmVkLiBXaGVuIHRoZSBwZW5jaWwgaXMgbG93ZXJlZCwgbW92aW5nIHRoZSB0dXJ0bGUgY2F1c2VzIHRoZSBwZW5jaWwgdG8gbGVhdmUgYSB0cmFpbCBvbiB0aGUgc2NyZWVuLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgdHVydGxlIGlzIGluaXRpYWxseSBhdCBjb29yZGluYXRlcyAoMCwgMCkgZmFjaW5nIGluIHRoZSBkaXJlY3Rpb24gb2YgaW5jcmVhc2luZyB5IGNvb3JkaW5hdGVzLCBwZW5jaWwgbG93ZXJlZC4gV2UgY2FuIG1hbmlwdWxhdGUgdGhlIHR1cnRsZSB3aXRoIHRoZSBmb2xsb3dpbmcgc2V0IG9mIGNvbW1hbmRzOiZuYnNwOzxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPkZEIHggJm5kYXNoOyBtb3ZlIHRoZSB0dXJ0bGUgeCB1bml0cyBmb3J3YXJkLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5MVCAmYWxwaGE7ICZuZGFzaDsgdHVybiB0aGUgdHVydGxlICZhbHBoYTsgZGVncmVlcyBjb3VudGVyLWNsb2Nrd2lzZS48XC9saT5cclxuXHQ8bGk+UlQgJmFscGhhOyAmbmRhc2g7IHR1cm4gdGhlIHR1cnRsZSAmYWxwaGE7IGRlZ3JlZXMgY2xvY2t3aXNlLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5QVSAmbmRhc2g7IHJhaXNlIHRoZSBwZW5jaWwuJm5ic3A7PFwvbGk+XHJcblx0PGxpPlBEICZuZGFzaDsgbG93ZXIgdGhlIHBlbmNpbC4mbmJzcDs8XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5Zb3VyIHByb2dyYW0gd2lsbCBiZSBnaXZlbiBhIHNldCBvZiByZWN0YW5nbGVzICh3aXRoIHNpZGVzIHBhcmFsbGVsIHRvIGNvb3JkaW5hdGUgYXhlcykgdGhhdCBuZWVkIHRvIGJlIGRyYXduIG9uIHRoZSBzY3JlZW4uIFRoZSB0dXJ0bGUgbWF5IGdvIG92ZXIgdGhlIHNhbWUgc2VnbWVudCB3aXRoIGl0cyBwZW5jaWwgbG93ZXJlZCBtdWx0aXBsZSB0aW1lcywgYnV0IGl0IGlzIG5vdCBhbGxvd2VkIHRvIGRyYXcgYW55dGhpbmcgb3RoZXIgdGhhbiB0aGUgZ2l2ZW4gcmVjdGFuZ2xlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgY2FsY3VsYXRlcyB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIHRpbWVzIHRoZSBwZW5jaWwgbXVzdCBiZSByYWlzZWQgaW4gb3JkZXIgdG8gZHJhdyBhbGwgdGhlIHJlY3RhbmdsZXMuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMTAwMCksIHRoZSBudW1iZXIgb2YgcmVjdGFuZ2xlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgZm9yIGludGVnZXJzIHgxLCB5MSwgeDIgYW5kIHkyICgmbWludXM7NTAwICZsZTsgeDEgJmx0OyB4MiAmbGU7IDUwMCksICgmbWludXM7NTAwICZsZTsgeTEgJmx0OyB5MiAmbGU7IDUwMCkgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuIFRoZSBwb2ludHMgKHgxLCB5MSkgYW5kICh4MiwgeTIpIGFyZSBkaWFnb25hbGx5IG9wcG9zaXRlIGNvcm5lcnMgb2YgYSByZWN0YW5nbGUuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBzbWFsbGVzdCBudW1iZXIgb2YgdGltZXMgdGhlIHBlbmNpbCBtdXN0IGJlIHJhaXNlZCB0byBkcmF3IHRoZSByZWN0YW5nbGVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d
접근 방법
- 이중 반복문을 통해 서로 다른 두 개의 직사각형을 탐색하며 유니온 파인드를 진행한다.
- 모든 반복문을 끝낸 뒤, 0, 0을 지나는 선분이 있는 지 확인하고, 있다면 집합의 개수를, 없다면 집합의 개수 + 1을 출력한다.
코드
# https://www.acmicpc.net/problem/3108
# 접근 방법
# 이중 반복문을 통해 서로 다른 두 개의 직사각형을 탐색하며 유니온 파인드를 진행한다.
# 모든 반복문을 끝낸 뒤, 0, 0을 지나는 선분이 있는 지 확인하고, 있다면 집합의 개수를, 없다면 집합의 개수 + 1을 출력한다.
def get_parent(x):
if parent[x] == x:
return x
parent[x] = get_parent(parent[x])
return parent[x]
def union_find(x1, x2):
x1_parent = get_parent(x1)
x2_parent = get_parent(x2)
if x1_parent < x2_parent:
parent[x2_parent] = x1_parent
else:
parent[x1_parent] = x2_parent
def intersect_check(i, j):
x01, y01, x02, y02 = square[i]
x11, y11, x12, y12 = square[j]
if x12 < x01 or x11 > x02 or y11 > y02 or y12 < y01 or (x01 < x11 < x12 < x02 and y01 < y11 < y12 < y02) or (x11 < x01 < x02 < x12 and y11 < y01 < y02 < y12):
return False
return True
n = int(input())
square = [list(map(int, input().split())) for _ in range(n)]
parent = [i for i in range(n)]
start_point = [0, 0]
for i in range(n):
for j in range(i+1, n):
if intersect_check(i, j):
union_find(i, j)
union_set = set()
intersect_point = 0
count = 0
for i in range(n):
x1, y1, x2, y2 = square[i]
if not intersect_point and ((x1 <= start_point[0] <= x2 and start_point[1] in [y1, y2]) or (y1 <= start_point[1] <= y2 and start_point[0] in [x1, x2])):
intersect_point = 1
idx = get_parent(i)
if idx not in union_set:
union_set.add(idx)
count += 1
print(count - intersect_point)