[백준] 3108 로고

문제소개

---

3108 로고는 DFS문제 입니다. 

5가지 명령을 수행하는 거북이가 있습니다. "5개의 명령을 수행한다"라고 되어 있기 때문에 복잡해 보이지만 우리가 생각할 것은 PU(연필을 올리는 명령)를 최소화하는 방법입니다. 

 

PU의 용도는 직사각형을 그릴 필요가 없는 좌표에서 PU명령어를 수행합니다. 문제에 주어진 직사각형 N개를 제외한 직사각형은 그릴 수 없다라고 명시되어 있기 때문입니다. 그렇다고 하면 직사각형을 그릴 때 교차되는 선분이 있거나 겹쳐지는 선분이 있는 경우는 PU명령을 수행하지 않고 연결된 직사각형을 그릴 수 있습니다.

 

문제풀이

---

10
9
8
7
6			2	2	2	2
5			2	3	3	2
4	1	1	2	3	3	2
3	1		2	2	4	4	4	4
2	1			1	4	5	5	4
1	1	1	1	1	4	5	5	4
0	1	2	3	4	4	4	4	4	9

 

1. 좌표(0,0) 에서 출발하며 연필을 내린 상태로 시작됩니다. 

2. 좌표(0,0)에선 직사각형을 그리지 않기 때문에 PU명령어로 연필을 들어야합니다.

3. PU명령어 수행

4. 1번 직사각형을 그리는 과정에서 2번을 만나면 2번을 따라 그리는 과정을 DFS로 구현하면 됩니다. 

5. 4번을 반복하다가 연결이 안되어 있는 5번 직사각형을 그리기 위해서 PU명령어로 연필을 들어야 합니다.

6. PU명령어를 수행합니다.

 

저는 이러한 과정을 처음에는 직사각형을 2차 배열 좌표로 표현해놓고 DFS를 구현했습니다. 그런데 곰곰히 생각해보면 연결된다는 말은 두 개의 직사각형이 교차하는 것을 이야기 합니다. 그러므로 직사각형을 2차 배열 좌표로 표현할 필요 없이 두 개의 직사각형이 겹치는지 여부만 판단하면 됩니다. O(N^2)

 

---

소스보기