문제
평면상에서 어떤 로봇이 수평 또는 수직으로 선을 그으면서 움직인다. 이 로봇은 처음 정해진 위치에서 시작하여 움직인 뒤 다시 처음 위치로 되돌아 온다.
로봇이 움직이는 방향은 위(UP), 아래(DOWN), 오른쪽(RIGHT), 왼쪽(LEFT) 4가지 뿐이며, 이는 각각 U, D, R, L로 표시된다. 또 움직인 거리는 양의 정수이다. 움직임은 방향과 거리로써 표현되는데 예를 들어 "R 3"이라고 하면 오른쪽으로 3만큼 움직인 것이다.
최종적인 궤적을 살펴보면 다양한 다각형이 생겨난다. 이 다각형중에서 그 내부에 다른 점이나 선분을 포함하지 않은 사각형을 단순 사각형이라고 한다. 문제는 주어진 궤적으로 만들어진 단순 사각형 중에서 가장 작은 면적의 단순 사각형을 구하는 것이다.
위의 그림에서 촤표(4, 9)는 출발점이고 로봇의 움직인은 R 7, D 5, L 10, U 3, ... 으로 진행된다. 위 그림에서 회색으로 표시한 부분이 가장 작은 면적의 단순 사각형이므로 이것이 답이 된다.
두 선분이 만나는 경우는 수직선분과 수평선분이 한 점에서 만나는 경우 뿐이며 수평선분과 수평선분, 수직선분과 수직선분이 서로 만나거나 겹치는 경우는 없다.
입력
첫째 줄에는 시작점의 x좌표와 y좌표가 하나의 빈칸을 사이에 두고 주어진다. 그 다음 줄에는 움직인 동작의 횟수 n이 주어진다. n은 100 이하의 정수이다. 그 다음 n개의 줄에는 움직임의 방향(U, D, R, L)과 거리가 하나의 빈칸을 사이에 두고 주어진다. 로봇의 움직임은 x, y 모두 1 이상 100 이하의 정수 좌표 내에서 이루어진다.
출력
가장 작은 면적을 갖는 단순 사각형의 왼쪽 아래 꼭짓점의 좌표를 첫째 줄에, 오른쪽 위 꼭짓점의 좌표를 둘째 줄에 출력하면 된다. 좌표의 출력은 x좌표, y좌표 순으로 하며 하나의 빈칸을 사이에 둔다. 가장 작은 면적의 단순 사각형이 여러 개인 경우에는 그 중에서 하나만 출력하면 된다. 만일 단순 사각형이 존재하지 않으면 첫째 줄에 0 을 출력한다.
https://www.acmicpc.net/problem/2648
풀이
먼저 로봇의 위치가 문제에서는 좌표평면상의 위치로 주어지므로,
우리는 2차원배열에 기록할때 예시그림을 상하반전 시킨 위치로 메모리화시킬것이다. (처음에 이부분을 잘 고려하고 시작해야 편하다)
필자는 꼭짓점이 만들어지는 두가지경우를 생각해보았다.
- 로봇이 방향을 트는 순간
- 두 직선이 교차하는 점
여기서 나온아이디어가, 좌, 우로 이동하는경우 가로줄로 보아 좌측점위치, 우측점위치를 width 벡터에,
상 하 로 이동하는경우 세로줄로 보아 상단점위치, 하단점위치를 각각
std::vector<pair<pair<int, int>, pair<int, int>>> width, height에 각각기록하였다.
이런식으로 가로줄, 세로줄 따로 width, height에 나누어 기록하며, 방향전환시, 꼭짓점위치를 vertex에 기록했다. <= 1번과정
다음으로 가로 세로 두 선분그룹이 직교할때 그 교차점이 꼭짓점으로보아 vertex에 기록하는 함수다. <= 2번과정
마지막으로, 꼭짓점을이용해서 사각형의 넓이를 찾는 함수다.
1,2 번의경우는 일직선상에 두 기준점이 놓인경우, 3번의경우는 두 기준점 사이 다른 꼭짓점이 하나만 있는경우면 사각형이만들어지지않고,
4번과같이 두 기준점사이 다른 꼭짓점이 정확히 2개가 생겨야 해당영역이 단순사각형인것이다.
마지막으로 출력할때 필자의경우 입력받은 좌표를 상하반전시켰으므로... 코드를 구현할때 이부분을 좀더 유연하게 짰으면 좀더 수월했을것이다.
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
/*
* 핵심 포인트
* 1. 모든 꼭짓점(방향전환시 생기는점, 두 선분이 교차하는점)
* 2. 하나의 꼭짓점을 기준으로 선정하고, 사각형이 되기위한 나머지 3 꼭짓점이 존재하는지
* 확인 => 있다면 넓이계산 없으면 반복
* 2-1. 위에서 꼭짓점들을 탐색할때 기준점의 x,y 기준으로 x+, x-, y+, y- 의 제각기범위를
* vertex 에서 탐색하면된다.
* 3. 넓이가 1~ 100까지인 사각형을 찾도록 브루트포스알고리즘을 써도되지만
* 좀더 효율적인 알고리즘을 찾아보았음
*/
using std::pair;
using std::vector;
typedef pair<int, int> p;
//width : <좌측점x1y1 , 우측점x2y2>
//height : <상단점x1y1 , 하단점x2y2>
//width갯수 X height갯수로 각각비교하여
//교차하는경우 꼭짓점으로 기록
vector<pair<p, p>> width, height;
//시작좌표 => 좌표평면을 상하반전 시킨것과 같음.
//map : 지나온 궤적들
int x, y, n;
int res_x1, res_y1, res_x2, res_y2;
//vertex : 꼭짓점 위치들만
bool vertex[100][100];
void findVertex() { //가로 세로 두선분이 교차시 생기는 꼭짓점들을 파악
int wn = width.size(), hn = height.size();
for (int i = 0; i < wn; i++) { //width탐색
//w_x1, w_y1 가로선분 좌측 좌표
//w_x2, w_y2 가로선분 우측 좌표
int w_x1 = width[i].first.first, w_y1 = width[i].first.second;
int w_x2 = width[i].second.first, w_y2 = width[i].second.second;
for (int j = 0; j < hn; j++) { //height 탐색
//h_x1, h_y1 세로선분 상단좌표
//h_x2, h_y2 세로선분 하단좌표
int h_x1 = height[j].first.first, h_y1 = height[j].first.second;
int h_x2 = height[j].second.first, h_y2 = height[j].second.second;
//printf("?? %d x %d => (%d,%d)ㅡ(%d,%d) // (%d,%d)ㅡ(%d,%d)\n", i, j, w_x1, w_y1, w_x2, w_y2, h_x1, h_y1, h_x2, h_y2);
if ((w_y1 <= h_y1 && h_y1 <= w_y2) &&
(h_x1 <= w_x1 && w_x1 <= h_x2)) { //두선분이 수직으로 교차한다면
int xx = w_x1, yy = h_y1; //교차하는 꼭짓점의 좌표
vertex[xx][yy] = true; //기록
}
else { //두선분이 안만나면 제외
continue;
}
}
}
}
int calculate() {
int min = 0x7fffffff;
for (int x1 = 0; x1 < 100; x1++) {
for (int y1 = 0; y1 < 100; y1++) {
if (vertex[x1][y1]) { //기준점1
for (int x2 = 0; x2 < 100; x2++) {
for (int y2 = 0; y2 < 100; y2++) {
if (x1 == x2 && y1 == y2) continue; //같은 점을잡으면 제외
if (vertex[x2][y2]) { //기준점2
//일직선상 이거나 이미 탐색한 기준점이면 제외
//x1,y1 이 항상 x2,y2 좌표보다 좌상단에 있는것
if (x1 >= x2) continue;
if (y1 >= y2) continue;
//두 기준점으로 만들어지는 사각형의 우상단 꼭짓점확인
if (!vertex[x1][y2]) continue; //없으면 제외
//만들어지는 사각형의 좌하단 꼭짓점확인
if (!vertex[x2][y1]) continue;
//여기까지오면 찾은것
int area = (x2 - x1) * (y2 - y1);
if (min > area) { //최솟값이면 기록
min = area;
res_x1 = x1; //좌표기록
res_y1 = y1;
res_x2 = x2;
res_y2 = y2;
}
}
}
}
}
}
}
if (min == 0x7fffffff)
return 0;
else
return min;
}
int main(void) {
scanf("%d%d%d", &y, &x, &n); //x, y를 행, 열 좌표로 두기위해 바꾸어 대입
x--; y--; //좌표평면상좌표는 1,1~ 100, 100이지만 실제 행열좌표는 0,0부터 시작하므로
for (int i = 0; i < 100; i++) //초기화
for (int j = 0; j < 100; j++)
vertex[i][j] = false;
//입력을 받아서 가로줄, 세로줄 그룹에 넣고
//방향전환했을시 vertext에 꼭짓점으로 기록
int prevFlag;
for (int i = 0, temp; i < n; i++) {
char c, junk;
int currentFlag = -1;
int xx=x, yy=y; //로봇이 움직이기전 시작좌표
scanf("%c", &junk); //줄바꿈문자 지움
scanf("%c%d", &c, &temp);
if (c == 'R') { //가로줄 그룹
currentFlag = 1;
y += temp;
width.push_back({ {xx, yy},{x, y} });
}
else if (c == 'L') { //가로줄 그룹
currentFlag = 2;
y -= temp;
width.push_back({ {x, y},{xx, yy} });
}
else if (c == 'D') { //세로줄 그룹
//좌표평면상의 down => 행열상 up
currentFlag = 4;
x -= temp;
height.push_back({ {x, y},{xx, yy} });
}
else if (c == 'U') { //세로줄 그룹
//좌표평면상의 down => 행열상 up
currentFlag = 3;
x += temp;
height.push_back({ {xx, yy},{x, y} });
}
if (i == 0)
prevFlag = currentFlag;
if (prevFlag != currentFlag) //현재 이동이 방향전환했다면
vertex[xx][yy] = true; //시작좌표 위치가 꼭짓점
prevFlag = currentFlag;
}
findVertex();
if (calculate() == 0) {
printf("0");
return 0;
}
else {
printf("%d %d\n%d %d", res_y1 + 1, res_x1 + 1, res_y2 + 1, res_x2 + 1);
return 0;
}
}