문제 상황
문제가 되는 파트의 난이도 자체가 높은 것은 아니다. 장애물이 격자 형태로 놓여 있고, 왼쪽 아래에서 출발해서 오른쪽 위로 가면 되는 간단한 파트다. 심지어 이 장애물도 게임을 킬 때마다 랜덤으로 배치되는 게 아니라 위치가 고정되어 있다. 문제는 처음에 어느 방향으로 서 있는지가 랜덤이라는 것이다. 안대를 꼈으니 방향을 알 방법이 없다.
N×N 격자가 있고, 2≤N≤20이다. 몇몇 칸에는 거대한 장애물이 있어서 지나갈 수 없고, 나머지는 비어 있어서 자유롭게 지나갈 수 있다. 격자 외부도 벽으로 둘러싸여 있어서 밖으로 나갈 수 없다. 주인공은 처음에 왼쪽 아래에 있고, 어느 방향으로 서 있는지는 모르지만 위와 오른쪽 중 하나인 것은 확실하다. 주인공은 매초 "전진", "좌회전", "우회전" 중 하나만 할 수 있다. 각 행동에는 1초가 걸린다. 전진하려고 하는데 앞에 장애물이나 벽이 있으면 그 자리에 그대로 있는다.
우리는 어느 방향으로 서 있는지에 관계 없이 오른쪽 위로 도착하도록 할 수 있는 가장 짧은 배열을 작성해야 한다. 도착하면 바로 컷신이 재생되므로 도착한 뒤 다른 칸으로 이탈할 일은 없다.
왼쪽 아래에서 오른쪽 위로 가면 됨 ⇒ 장애물은 고정되어있음 ⇒ 서있는 방햐잉 랜덤 ⇒ 위와 오른쪽중 하나의 위치로 서있음 매번 전진 좌회전 우회전
입력
첫 줄에는 N이 주어진다.
그 다음 N줄에는 격자의 행을 나타내는 길이 N의 스트링이 주어진다. E는 빈 칸이고, H는 장애물이다.
왼쪽 아래와 오른쪽 위는 무조건 E고, 왼쪽 아래에서 오른쪽 위로 가는 경로가 무조건 존재한다.
출력
3
EHE
EEE
EEE
왼쪽 아래와 오른쪽 위가 반드시 갈수있는 곳이고
과정
느낌이 온다. DP를 이용해 특정 지점에 도달할 수 있는 최소의 move를 수로 저장해놔야할 것 그런데 정답은 둘중에 큰것을 저장해야함. 배열을 따로 저장하는게 유효할까?
그리고 이 두 개의 방식이 양쪽 모두에서 유효해야함
단순히 특정 위치가 아니라 방향까지지정한 DP를 함으로써 좀 더 자세하게는 구할 수 있다. 그렇다 치더라도 이 문제는 동일한 행동으로 동일한 위치에 오는게 필요함.
그냥 귀찮으니 하나를 먼저 넣고 다른 하나가 들어가는 최소의 방법을 구하면 안되나?
아니면 하나를 먼저 모든 방향에 대해 약 20 * 20 * 4 ㅈㄴ 적음 1600번에 대해서 전부 구함 하튼
그다음에 한점을 기준으로 쭉쭉 움직인다. 다른점은 위치를 체크하는 정도로만, 하나가 들어가면 그때의 값 + DP에 저장된 값 더해서 최소값으로 설정하고 얘보다 낮은 애들에 대해서만 작업 반복하면 빠르게 끝날듯 이건 이미 하나가 들어갔을때를 가정하기때문에 가능함
반대도 해놓아야겠지. 또한 이러면 한번 간 곳에 다시 갈 필요가 없음 그래서 순수 다익스트라로 두번 4번 하면 되는 수준임
문제가 하나 있다 근데 which is ..
끝점부터 계산하는걸로 바꾸려고했다 방향이 다르다보니 저장되는 곳이 다름. 물론 그건있다. 갈때는 올때의 역순이니 반대로 행동해야한다. 즉방향이 반대 동쪽으로 움직였다면 서쪽으로 움직이는 것으로 해주면 됨. 그렇지만 이런 행동은 비약으로 작동할 때가 많은데
얼마나 더 더럽게 해야하는거야 시발
어쨋든 모든 점의 모든 방향에서 목적지까지의의 최소 길이만 구해주면 될 일 정말 그걸로 충분한 것인가? 그리고 시작점이 사실상 두개여야 한다는 것도 문제 그것도 입력을 두개로 함으로써 완성되는건가?
8 0 1 북 5 4 1 6 5 2
7 0 1 동 4 3 2 5 4 3
6 0 1 남 5 4 3 6 5 4
7 0 1 서 6 5 2 7 6 3
EHE
EEE
EEE
혼자서는 세상을 구할 수 없다.
내가 지은 일을 확실히 매듭 짖는다. 부족함을 인정해야한다. 가장 훌륭한 자세
이 문제에서 난 이것을 모른다
- 다익스트라로 모든 점, 모든 방향에서 끝점까지의 거리를 얻었고, 시적점에서 모든점, 모든 방향까지의 비용을 구했다
- 다시 돌아와서 난 모든 점, 모든 방향에서 끝점까지의 거리를 구했다. 이걸 토대로 두개의 점을 동기화한 BFS를 통해서 (두번) 각각의 점들이 끝에 도달했을때 발생한 비용과 그떄 다른 점이있는 위치를 구해서 DP값을 계산함 그런데 그걸로도 부족했는지 결과물이 안나옴.
#include <iostream>
#include <queue>
using namespace std;
#define MAXN 20
int dist[MAXN][MAXN][MAXN][MAXN][4][4];
char map[MAXN][MAXN];
int N;
struct node{
int x1;
int y1;
int x2;
int y2;
int dir1;
int dir2;
};
queue<node> q;
// 동남서북
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
int dirs[3] = {-1,0,1};
// 방향
int bfs(){
// 첫노드 설정 북 동
q.push({N-1,0,N-1,0,3,0});
dist[N-1][0][N-1][0][3][0] = 1;
// 거리 설정
int time = 0;
while (!q.empty()){
int q_size= q.size();
int x1 = q.front().x1;
int y1 = q.front().y1;
int x2 = q.front().x2;
int y2 = q.front().y2;
int dir1 = q.front().dir1;
int dir2 = q.front().dir2;
if (x1 == 0 && x2 == 0 && y1 == N-1 && y2 == N-1) {
// 그냥 쌩으로 BFS를 했다??
return dist[x1][y1][x2][y2][dir1][dir2]-1;
}
q.pop();
for (int i = 0;i < 3; i++){
int ndir1 = dir1;
int ndir2 = dir2;
int nx1 = x1;
int ny1 = y1;
int nx2 = x2;
int ny2 = y2;
if (!(x1 == 0 && y1 == N-1)){
ndir1 = (4 + dir1 + dirs[i])%4;
// 방향을 움직인게 아닐떄만
if (ndir1 == dir1){
nx1 += dx[dir1];
ny1 += dy[dir1];
// 장애물이거나 끝단이면 뒤로 다시 이동
if (nx1 < 0 || ny1 < 0 || nx1 >= N || ny1 >=N || map[nx1][ny1] == 'H'){
nx1 -= dx[dir1];
ny1 -= dy[dir1];
}
}
}
if (!(x2 == 0 && y2 == N-1)){
ndir2 = (4+ dir2 + dirs[i])%4;
// 방향을 움직인게 아닐때만
if (ndir2 == dir2){
nx2 += dx[dir2];
ny2 += dy[dir2];
// 장애물이거나 끝단이면 뒤로 다시 이동
if (nx2 < 0 || ny2 < 0 || nx2 >= N || ny2 >=N || map[nx2][ny2] == 'H'){
nx2 -= dx[dir2];
ny2 -= dy[dir2];
}
}
}
if (dist[nx1][ny1][nx2][ny2][ndir1][ndir2]) continue;
dist[nx1][ny1][nx2][ny2][ndir1][ndir2] = dist[x1][y1][x2][y2][dir1][dir2]+1;
q.push({nx1,ny1,nx2,ny2,ndir1,ndir2});
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N;
for (int i = 0 ;i <N;i++){
for (int j =0;j<N;j++){
cin >> map[i][j];
}
}
cout << bfs();
return 0;
}
특별한 알고리즘이 없음 그냥 BFS 조금 다른점이라면 결국 마제막에 캐치한대로 좌표까지 신경써줘야 한다는 점 정도? 내 멍청함이 조금 돋보이는 문제풀이였다