14923 - c++

https://www.acmicpc.net/problem/14923

14923번: 미로 탈출

요약

1. 현재 나의 위치와 탈출가능한 위치가 있다

2. 벽을 딱 한번 부술 수 있다. 벽을 부수고 최단 경로를 구하는 것

---

아이디어

예전에 비슷한 문제를 풀었던 적이 있다. 벽을 부순 상태일 때의 배열을 따로 만드는 방법으로 풀었던 기억이 있다.

그것과 비슷하게 dist [n][m][2]라는 배열을 만들고 

dist[a][b][0] // 벽을 부수지 않은 상태
dist[a][b][1] // 벽을 부순 상태

이런 방식으로 구현 하려 했다.

그런데 주의해야 할 점이 있다면 밑의 그림이다

나의 위치를 표현 하는게 1 < Hx, Hy, Ex, Ey <= 1000 1부터 표현한다. 배열에서 (0, 0)이 위치로 봤을 때 (1,1)이 되는 것

이 부분을 못보고 넘어가 원하지 않은 결과들을 많이 만났다. 항상 조건들을 잘 보도록 하자...

 

그럼 구현해 보자

---

CODE

//미로 탈출 홍익이와 마녀
#include <bits/stdc++.h>

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

int n, m;
int hx, hy, ex, ey;

int board[1001][1001];
int dist[1001][1001][2];

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

queue<tuple<int, int, int>> Q;

bool OOB(int x, int y){
  return x < 1 || x > n || y < 1 || y > m;
}

int main(){
  init();
  cin >> n >> m;
  cin >> hx >> hy >> ex >> ey;

// dist 초기화
  for(int i =0; i <= n; ++i)
    for(int j =0; j <= m; ++j)
      for(int k =0; k < 2; ++k)
        dist[i][j][k] = -1;

//보드 입력
  for(int i = 1; i <= n; ++i)
    for(int j =1; j <= m; ++j)
      cin >> board[i][j];
  
  //가장 처음 나의 위치를 설정한다.
  Q.push({hx, hy, 0});
  dist[hx][hy][0] = 0; //행렬 은 1행 1열 이렇게 나타냄 0행 0열은 없음

//bfs 실행
  while(!Q.empty()){
    int x, y, st;
    tie(x, y, st) = Q.front(); Q.pop();
    
    //인접한 네 방향 조사
    for(int dir = 0; dir < 4; ++dir){
      int nx = x + dx[dir];
      int ny = y + dy[dir];

      //만약 탈출 위치에 도착했다면 시간 출력 후 return
      if(nx == ex && ny == ey){
        cout << dist[x][y][st] + 1 << '\n';
        return 0;
      }

      //OOB (Out Of Bounds) : 다음 인덱스가 배열 밖으로 나갔는지 검사
      //dist != 1: 전에 방문 한적이 있는 곳이라면 continue;
      if(OOB(nx, ny) || dist[nx][ny][st] != -1)continue;

      //현재 상태가 벽을 부수지 않은 상태 이면서 다음 인덱스가 벽이라면 벽 부숴!
      //부수고 Q에 잘 Push 해주고 방문 시간 저장 해준다음 continue
      if(st == 0 && board[nx][ny] == 1){
        Q.push({nx, ny, 1});
        dist[nx][ny][1] = dist[x][y][st] + 1;
        continue;
      }
      //현재 벽을 부순 상태이고 다음 요소가 벽이라면 continue
      if(board[nx][ny] == 1)continue;

      //여기 까지 잘 왔다면 Q에 Push해주고 방문 시간을 저장한다.
      Q.push({nx, ny, st});
      dist[nx][ny][st] = dist[x][y][st] + 1;
    }
  }
  
  //return 되지 않고 여기 까지 왔다면 탈출 실패 했다는 말이니 -1 출력
  cout << -1;
  return 0;
}

로직 하나하나에 대한 해석은 주석으로 남겨뒀다 BFS를 알고 있다며 이해하기 쉬울 것 같다.

---

문제를 풀며

예전에 비슷한 문제를 풀었던 기억이 있다 보니 이렇게 하면 무조건 풀 수 있겠다는 확신이 있어 수월 했다.

쉬운 문제를 계속 풀어 봤자 공부는 되지 않는다. 더 어려운걸 계속 도전하자