문제 요약
로봇이 출발지에서 도착지까지 이동할 때 경로 출력하기
(앞으로 2칸 이동 가능, 회전 정보까지 포함해야 함)
입력형식
- 5 ≤ H, W ≤ 25
- 사수는 한 번 이상의 A 명령을 내렸다. 따라서, 로봇이 방문한 칸 수는 최소 3개 이상이다.
- 이 문제의 경우 목표를 달성할 수 있는 방안이 여러개 일 수 있으며 그 중 아무 것이나 출력해도 답으로 처리된다.
- 아래의 입출력 예제를 보면, 하나의 입력에 대해 각각 달성할 수 있는 방안(출력)이 2개씩 존재한다. [예제 1, 예제 2], [예제 3, 예제 4] 두 가지 방안 중 하나가 정답으로 출력된 경우 정답으로 인정된다.
출력형식
첫 번째 줄에 격자판의 세로 크기 H와 가로 크기 W가 공백 하나를 사이로 두고 주어진다. 다음에는 사수가 넘겨준 지도가 주어진다. H개의 줄에 W개의 문자가 주어지는데, 이 중 i(1 ≤ i ≤ H)번째 줄의 j(1 ≤ j ≤ W)번째 문자는, 사수가 조작한 로봇이 i행 j열을 방문했다면 '#'이고, 방문하지 않았다면 '.'이다.
해결 방법
- 맵을 돌면서 로봇 경로의 시작점을 찾는다. 시작점은 상하좌우 중 한 방향으로만 경로가 이어져있다.
- 시작점을 기준으로 끝날때 까지 DFS하고, 짝수 번째 지점 좌표를
whole_path배열에 저장한다. whole_path를 다시 돌면서, 이전 지점 좌표와 비교하여 방향 전환과 이동 과정을 출력한다.
1: 시작점 찾기
// 시작점 찾기
for (int i=0; i<height; i++) {
for (int j=0; j<width; j++) {
if (whole_map[i][j] == 1) {
cnt = 0;
cnt_b = cnt_l = cnt_r = cnt_t = 0;
// 위
if (i >= 1 && whole_map[i-1][j] == 1)
cnt_t++;
// 아
if (i <= height-2 && whole_map[i+1][j] == 1)
cnt_b++;
// 왼
if (j >= 1 && whole_map[i][j-1] == 1)
cnt_l++;
// 오
if (j <= width-2 && whole_map[i][j+1] == 1)
cnt_r++;
cnt = cnt_b + cnt_l + cnt_r + cnt_t;
if (cnt == 1) {
cout << i+1 << " " << j+1 << endl;
if (cnt_b) cout << "v" << endl;
else if (cnt_l) cout << "<" << endl;
else if (cnt_r) cout << ">" << endl;
else if (cnt_t) cout << "^" << endl;
dfs(i, j);
}
}
}
}2: DFS 및 경로 저장
겹치는 등수를 세기 위한cnt, 전체 등수를 계산하기 위한prize를 만들고 리스트를 돌면서 조건에 따라 등수를 대입했다.
void dfs(int x, int y) {
// Path를 리스트에 추가
// cout << x << y << " ";
whole_map[x][y] = -1;
if (path_cnt % 2 == 0) {
whole_path[path_cnt/2][0] = x+1;
whole_path[path_cnt/2][1] = y+1;
}
path_cnt++;
// 위
if (x >= 1 && whole_map[x-1][y] == 1) {
dfs(x-1, y);
}
// 아
else if (x <= height-2 && whole_map[x+1][y] == 1) {
dfs(x+1, y);
}
// 왼
else if (y >= 1 && whole_map[x][y-1] == 1) {
dfs(x, y-1);
}
// 오
else if (y <= width-2 && whole_map[x][y+1] == 1) {
dfs(x, y+1);
}
}3: 방향 전환과 이동 과정 출력
이진 탐색으로 해당 참가자의 등수를 찾았다.
void Pathfinder() {
cout << "A";
for (int i=1; i<MAX_SIZE-1; i++) {
if (whole_path[i+1][0] == 0 && whole_path[i+1][1] == 0) break;
// R,B
if (whole_path[i-1][0] < whole_path[i+1][0] && whole_path[i-1][1] < whole_path[i+1][1]) {
// x가 같았다면
if (whole_path[i-1][0] == whole_path[i][0]) {
cout << "R";
}
// y가 같았다면
else if (whole_path[i-1][1] == whole_path[i][1]) {
cout << "L";
}
}
// L,T
else if (whole_path[i-1][0] > whole_path[i+1][0] && whole_path[i-1][1] > whole_path[i+1][1]) {
// x가 같았다면
if (whole_path[i-1][0] == whole_path[i][0]) {
cout << "R";
}
// y가 같았다면
else if (whole_path[i-1][1] == whole_path[i][1]) {
cout << "L";
}
}
// R,T
else if (whole_path[i-1][0] > whole_path[i+1][0] && whole_path[i-1][1] < whole_path[i+1][1]) {
// x가 같았다면
if (whole_path[i-1][0] == whole_path[i][0]) {
cout << "L";
}
// y가 같았다면
else if (whole_path[i-1][1] == whole_path[i][1]) {
cout << "R";
}
}
// L,B
else if (whole_path[i-1][0] < whole_path[i+1][0] && whole_path[i-1][1] > whole_path[i+1][1]) {
// x가 같았다면
if (whole_path[i-1][0] == whole_path[i][0]) {
cout << "L";
}
// y가 같았다면
else if (whole_path[i-1][1] == whole_path[i][1]) {
cout << "R";
}
}
cout << "A";
}
}얻어가는 것
- 재귀를 이용한 DFS 구현 (유사코드)
DFS() {
if (탈출 조건)
return
수행문
dfs(x-1, y)
dfs(x+1, y)
dfs(x, y-1)
dfs(x, y+1)
}
Mechanical Engineering, SKKU