문제 이해 단계
https://www.acmicpc.net/problem/1726
1726번: 로봇
많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는
www.acmicpc.net
MxN짜리 맵에 입력으로 출발 좌표와 목적 좌표가 주어진다.
출발지에서 로봇이 출발하는데
로봇이 할 수 있는 행동은 아래의 2가지이다.
명령 1. Go k : k는 1,2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸만큼 움직인다.
명령 2. Turn dir : dir은 left 또는 right이며, 각각 왼쪽 또는 오른쪽으로 90도 회전한다.
로봇을 목적지에 도착시키고,
원하는 방향을 바라보게 하는데 걸리는 최소 명령 횟수를 구하는 문제
문제 접근 단계
맵의 크기는 최대 100 x 100 까지만 가능하다.
그렇게 크지는 않다.
탐색으로 인한 시간초과는 그렇게 신경 쓰지 않아도 되는 걸로 보인다.
그리고 중요한 것은 동서남북의 방향을 각각 1,2,3,4로 정해줬다는 것이다.
바꾸면 안 된다는 것은 아니지만,
입력으로 이 방향 약속대로 들어온다는 것을 기억해야 한다.
어떤 유형으로 봐야 할까?
해당 문제는 2차원 맵에 벽이 존재하고, 최단 거리를 찾는 문제이다.
또한 상하좌우가 존재하고, 이동을 해야 한다.
그래프 탐색 문제라는 것을 쉽게 유추할 수 있다.
하지만 문제가 되는 점은 로봇은 앞으로 1~3칸밖에 이동하지 못하고,
왼쪽 혹은 오른쪽으로 90도씩 회전한다.
일반적인 그래프 탐색과는 조금 다르게 접근해야 할 것 같다.
존재하는 경우의 수
그래프 탐색을 위해서 꼭 들어가야 하는 것이 방문 확인(visited) 배열이 있다.
기본적으로는 맵의 각 칸마다 하나의 visited배열을 가지고 있다.
그런데 잘 생각해 보면,
이 문제는 한 칸에서도 총 4가지 상태로 존재할 수 있다.
무슨 소리냐면, 같은 칸이라도
북쪽을 바라보는 경우,
남쪽을 바라보는 경우,
서쪽을 바라보는 경우,
동쪽을 바라보는 경우
총 4가지 경우가 있다는 뜻이다.
즉 맵의 각 칸마다 동서남북을
따로 체크할 수 있는 배열을 만들어줘야 한다.
최단거리 계산
위의 사실은 인지한 채,
그래프 탐색을 통해 최단거리를 구하기 위해 BFS를 사용하기로 했다.
DFS를 사용해도 되긴 하는데,
재귀함수를 사용하면 더 복잡해질 것 같아서
BFS로 더 직관적으로 하는 게 더 나아 보였다.
큐 안에 방향 정보와 이동 횟수 정보를
같이 담아서 BFS를 진행한다.
BFS 도중 할 수 있는 행동은 총 2가지이다.
1 ~ 3칸 앞으로 이동하기
1칸 ~ 3칸까지 바라보고 있던 칸이 이동 가능한 칸인지 체크한다.
가능한 칸이면 그 칸을 방문처리하고 큐에 넣는다.
이때 방향 정보도 함께 큐에 넣는다.
이때 1칸에서 3칸까지 순차적으로 넣는데,
|2칸째에 이동불가능한 칸이면
continue가 아닌 break으로 3칸은 검사하지 않는다.
왜냐하면 연속된 움직임인데,
2번째 칸을 이동하지 못했는데, 3번째 칸을 이동할 순 없기 때문이다.
왼쪽 혹은 오른쪽으로 90도 회전
두 번째로는 방향을 오른쪽으로 돌린 정보를 큐에 넣고,
왼쪽으로 돌린 정보를 큐에 넣는다.
이때도 마찬가지로 해당 visited배열이
이미 방문처리가 되었다면 큐에 집어넣지 않는다.
위와 같은 BFS를 반복하다가
큐에 있던 어떤 값이 도착지점에 있던 값과
방향이 같아지면 그 횟수를 반환하고 종료한다.
이제 자세한 구현은 코드를 통해 알아보자.
문제 구현 단계
// 좌표와 방향 정보를 담음
struct Info{
int x;
int y;
int dir;
};
// 동 서 남 북
int dx[] = {0,0,0,1,-1};
int dy[] = {0,1,-1,0,0};
int N,M;
int map[101][101] = {0,};
// 방문확인 좌표
bool visited[101][101][5] = {false,};
Info sPoint; // 출발 좌표
Info ePoint; // 도착 좌표
// 왼쪽 혹은 오른쪽으로 방향을 돌리는 코드
int setDirect(int dir, char c){
// 각 회전에 따라 매핑
switch(c){
case 'R':
if(dir == 1) return 3;
else if(dir == 2) return 4;
else if(dir == 3) return 2;
else if(dir == 4) return 1;
case 'L':
if(dir == 1) return 4;
else if(dir == 2) return 3;
else if(dir == 3) return 1;
else if(dir == 4) return 2;
}
return -1;
}필요한 변수와 함수에 대해 설명하기 위해 따로 올렸다.
dx [], dy []는 문제 설명대로 매핑해 줬고,
정보를 좀 더 편하게 보기 위해 좌표와
방향정보를 담고 있는 Info라는 구조체를 만들었다.
그리고 아까 언급했던 대로 방문확인용 좌표는
동서남북 좌표를 담기 위해 3차원 배열로 선언했다.
마지막 배열이 5인 이유는 마지막 인덱스가 4이기 때문이다.
setDirect 함수는 왼쪽 혹은 오른쪽으로 방향을 돌리는 것이다.
문제에서 매핑해 준 동서남북에 따라 왼쪽, 오른쪽으로 돌려주는 것이다.
왼쪽과 오른쪽이 각각 다르기 때문에 하드코딩 해줬다.
int bfs(){
queue<pair<Info,int>> q; // 큐에는 방향 정보와 횟수 정보가 들어가있음
q.push({sPoint,0});
visited[sPoint.x][sPoint.y][sPoint.dir] = true;
while(!q.empty()){
int x = q.front().first.x;
int y = q.front().first.y;
int dir = q.front().first.dir;
int count = q.front().second;
q.pop();
// 도착좌표와 방향과 좌표가 같아지면 횟수 반환하고 종료
if(x == ePoint.x && y == ePoint.y
&& dir == ePoint.dir) return count;
// 1 ~ 3칸 이동하기
for(int i = 1; i <= 3; i++){
int nx = x + dx[dir] * i;
int ny = y + dy[dir] * i;
// 맵을 벗어나거나, 벽을 만난다면 해당 이동 종료
if(nx < 1 || ny < 1 || nx > N
|| ny > M || map[nx][ny] == 1) break;
// 이미 이동했던 좌표였으면 continue
if(visited[nx][ny][dir]) continue;
visited[nx][ny][dir] = true;
Info tmp = {nx,ny,dir};
q.push({tmp,count+1}); // 이동이므로 +1
}
// 회전
int ldir = setDirect(dir,'L');
int rdir = setDirect(dir,'R');
// 왼쪽 회전
if(!visited[x][y][ldir]){
visited[x][y][ldir] = true;
Info tmp = {x,y,ldir};
q.push({tmp,count+1});
}
// 오른쪽 회전
if(!visited[x][y][rdir]){
visited[x][y][rdir] = true;
Info tmp = {x,y,rdir};
q.push({tmp,count+1});
}
}
return -1;
}이제 핵심이 되는 BFS 함수이다.
큐에는 방향 정보와 횟수 정보가 포함되어 있다.
최종적으로는 큐에 담겨있던 값이
도착 좌표와 같아지면 횟수를 반환하고 종료하는 것이다.
그리고 바라보는 방향으로 1 ~ 3 칸 이동한다.
위에서 말한 대로 1칸부터 시작하여 중간에 벽이나 범위를 벗어난다면
break으로 뒤에 남은 칸들의 이동을 하지 못하도록 한다.
예외적으로 이미 방문한 배열에 대해서는 break이 아닌 continue를 한다.
왜냐하면 벽으로 막혀있는 것이 아니면 1칸은 이미 이동했을 수도 있지만,
2칸은 이동 안 했을 수도 있으니까
그리고 setDirect를 이용하여 왼쪽 오른쪽으로 돌려주고 방향을 설정한다.
그 방향을 방문한 기록이 없다면 그 방향을 큐에 넣는다.
이러한 과정을 계속 반복한다. 여기까지가 핵심 코드의 설명의 끝이다.
이제 아래에 전체 코드를 올리고 끝내겠다.
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
// 좌표와 방향 정보를 담음
struct Info{
int x;
int y;
int dir;
};
// 동 서 남 북
int dx[] = {0,0,0,1,-1};
int dy[] = {0,1,-1,0,0};
int N,M;
int map[101][101] = {0,};
// 방문확인 좌표
bool visited[101][101][5] = {false,};
Info sPoint; // 출발 좌표
Info ePoint; // 도착 좌표
// 왼쪽 혹은 오른쪽으로 방향을 돌리는 코드
int setDirect(int dir, char c){
// 각 회전에 따라 매핑
switch(c){
case 'R':
if(dir == 1) return 3;
else if(dir == 2) return 4;
else if(dir == 3) return 2;
else if(dir == 4) return 1;
case 'L':
if(dir == 1) return 4;
else if(dir == 2) return 3;
else if(dir == 3) return 1;
else if(dir == 4) return 2;
}
return -1;
}
int bfs(){
queue<pair<Info,int>> q; // 큐에는 방향 정보와 횟수 정보가 들어가있음
q.push({sPoint,0});
visited[sPoint.x][sPoint.y][sPoint.dir] = true;
while(!q.empty()){
int x = q.front().first.x;
int y = q.front().first.y;
int dir = q.front().first.dir;
int count = q.front().second;
q.pop();
// 도착좌표와 방향과 좌표가 같아지면 횟수 반환하고 종료
if(x == ePoint.x && y == ePoint.y
&& dir == ePoint.dir) return count;
// 1 ~ 3칸 이동하기
for(int i = 1; i <= 3; i++){
int nx = x + dx[dir] * i;
int ny = y + dy[dir] * i;
// 맵을 벗어나거나, 벽을 만난다면 해당 이동 종료
if(nx < 1 || ny < 1 || nx > N
|| ny > M || map[nx][ny] == 1) break;
// 이미 이동했던 좌표였으면 continue
if(visited[nx][ny][dir]) continue;
visited[nx][ny][dir] = true;
Info tmp = {nx,ny,dir};
q.push({tmp,count+1}); // 이동이므로 +1
}
// 회전
int ldir = setDirect(dir,'L');
int rdir = setDirect(dir,'R');
// 왼쪽 회전
if(!visited[x][y][ldir]){
visited[x][y][ldir] = true;
Info tmp = {x,y,ldir};
q.push({tmp,count+1});
}
// 오른쪽 회전
if(!visited[x][y][rdir]){
visited[x][y][rdir] = true;
Info tmp = {x,y,rdir};
q.push({tmp,count+1});
}
}
return -1;
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin >> N >> M;
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++) cin >> map[i][j];
int x,y,dir;
cin >> x >> y >> dir;
sPoint = {x,y,dir};
cin >> x >> y >> dir;
ePoint = {x,y,dir};
cout << bfs();
}
시행착오
아이디어나 풀이는 80% 정도는 근접하게 갔던 것 같다.
중요한 것은 역시나 구현이 문제였다. 그리고 디테일이 부족했다.
실수했던 부분은 동서남북을 내 마음대로 정의한 것,
해당 문제를 DFS로 풀어서 복잡하게 만들어버린 것.
이 두 가지 정도인 것 같다..
오랜만에 BFS한테 혼쭐이 났다.
토스아이디
toss.me