[모의 SW 역량테스트] 1953. 탈주범 검거

[모의 SW 역량테스트] 탈주범 검거

---

1. 이해하기

• 지하 터널은 총 7 종류의 터널 구조물로 구성되어 있다.
• 탈주범은 1시간에 인접한 네 방향으로 1 이동이 가능하다.
• 경과된 시간이 주어질 때 탈주범이 위치할 수 있는 장소의 개수를 구해야 한다.

---

2. 구현하기

• 현재 위치한 지하 터널과 다음에 이동할 지하 터널을 비교해서 이동할 수 있는 곳인지 판별해야 한다. 또한 지하 터널이 없는 곳은 탈주범이 이동할 수 없다.

  bool can_not_move(int x, int y, int nx, int ny, int d) {
      if(nx < 0 or nx >= N or ny < 0 or ny >= M or dist[nx][ny] != -1 or map[nx][ny] == 0) return true;
      if(map[x][y] == 1) {
          if(d == 0 and (map[nx][ny] == 3 or map[nx][ny] == 4 or map[nx][ny] == 7)) return true;
          if(d == 1 and (map[nx][ny] == 3 or map[nx][ny] == 5 or map[nx][ny] == 6)) return true;
          if(d == 2 and (map[nx][ny] == 2 or map[nx][ny] == 6 or map[nx][ny] == 7)) return true;
          if(d == 3 and (map[nx][ny] == 2 or map[nx][ny] == 4 or map[nx][ny] == 5)) return true;
      } else if(map[x][y] == 2) {
          if(d == 0 and (map[nx][ny] == 3 or map[nx][ny] == 4 or map[nx][ny] == 7)) return true;
          if(d == 1 and (map[nx][ny] == 3 or map[nx][ny] == 5 or map[nx][ny] == 6)) return true;
          if(d == 2 or d == 3) return true;
      } else if(map[x][y] == 3) {
          if(d == 0 or d == 1) return true;
          if(d == 2 and (map[nx][ny] == 2 or map[nx][ny] == 6 or map[nx][ny] == 7)) return true;
          if(d == 3 and (map[nx][ny] == 2 or map[nx][ny] == 4 or map[nx][ny] == 5)) return true;
      } else if(map[x][y] == 4) {
          if(d == 1 or d == 2) return true;
          if(d == 0 and (map[nx][ny] == 3 or map[nx][ny] == 4 or map[nx][ny] == 7)) return true;
          if(d == 3 and (map[nx][ny] == 2 or map[nx][ny] == 4 or map[nx][ny] == 5)) return true;
      } else if(map[x][y] == 5) {
          if(d == 0 or d == 2) return true;
          if(d == 1 and (map[nx][ny] == 3 or map[nx][ny] == 5 or map[nx][ny] == 6)) return true;
          if(d == 3 and (map[nx][ny] == 2 or map[nx][ny] == 4 or map[nx][ny] == 5)) return true;
      } else if(map[x][y] == 6) {
          if(d == 0 or d == 3) return true;
          if(d == 1 and (map[nx][ny] == 3 or map[nx][ny] == 5 or map[nx][ny] == 6)) return true;
          if(d == 2 and (map[nx][ny] == 2 or map[nx][ny] == 6 or map[nx][ny] == 7)) return true;
      } else if(map[x][y] == 7) {
          if(d == 1 or d == 3) return true;
          if(d == 0 and (map[nx][ny] == 3 or map[nx][ny] == 4 or map[nx][ny] == 7)) return true;
          if(d == 2 and (map[nx][ny] == 2 or map[nx][ny] == 6 or map[nx][ny] == 7)) return true;
      }
      return false;
  }

• 맨홀뚜껑의 위치에서 시작해 주어진 시간이 지나고 난 후 탈주범이 위치할 수 있는 곳의 수를 구한다.

  int bfs() {
      memset(dist,-1,sizeof(dist));
      queue<Point> q;
      q.push({R,C});
      int ret = 0;
      dist[R][C] = 1;
      while(!q.empty()) {
          int x = q.front().x, y = q.front().y; q.pop();
          if(dist[x][y] <= L) ret++;
          else break;
          for(int i = 0; i < 4; i++) {
              int nx = x+dx[i], ny = y+dy[i];
              if(can_not_move(x,y,nx,ny,i)) continue;
              q.push({nx,ny});
              dist[nx][ny] = dist[x][y]+1;
          }
      }
      return ret;
  }

---

3. 전체 코드

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
struct Point{
    int x,y;
};
int map[50][50];
int dist[50][50];
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
int N,M,R,C,L;

bool can_not_move(int x, int y, int nx, int ny, int d) {
    if(nx < 0 or nx >= N or ny < 0 or ny >= M or dist[nx][ny] != -1 or map[nx][ny] == 0) return true;
    if(map[x][y] == 1) {
        if(d == 0 and (map[nx][ny] == 3 or map[nx][ny] == 4 or map[nx][ny] == 7)) return true;
        if(d == 1 and (map[nx][ny] == 3 or map[nx][ny] == 5 or map[nx][ny] == 6)) return true;
        if(d == 2 and (map[nx][ny] == 2 or map[nx][ny] == 6 or map[nx][ny] == 7)) return true;
        if(d == 3 and (map[nx][ny] == 2 or map[nx][ny] == 4 or map[nx][ny] == 5)) return true;
    } else if(map[x][y] == 2) {
        if(d == 0 and (map[nx][ny] == 3 or map[nx][ny] == 4 or map[nx][ny] == 7)) return true;
        if(d == 1 and (map[nx][ny] == 3 or map[nx][ny] == 5 or map[nx][ny] == 6)) return true;
        if(d == 2 or d == 3) return true;
    } else if(map[x][y] == 3) {
        if(d == 0 or d == 1) return true;
        if(d == 2 and (map[nx][ny] == 2 or map[nx][ny] == 6 or map[nx][ny] == 7)) return true;
        if(d == 3 and (map[nx][ny] == 2 or map[nx][ny] == 4 or map[nx][ny] == 5)) return true;
    } else if(map[x][y] == 4) {
        if(d == 1 or d == 2) return true;
        if(d == 0 and (map[nx][ny] == 3 or map[nx][ny] == 4 or map[nx][ny] == 7)) return true;
        if(d == 3 and (map[nx][ny] == 2 or map[nx][ny] == 4 or map[nx][ny] == 5)) return true;
    } else if(map[x][y] == 5) {
        if(d == 0 or d == 2) return true;
        if(d == 1 and (map[nx][ny] == 3 or map[nx][ny] == 5 or map[nx][ny] == 6)) return true;
        if(d == 3 and (map[nx][ny] == 2 or map[nx][ny] == 4 or map[nx][ny] == 5)) return true;
    } else if(map[x][y] == 6) {
        if(d == 0 or d == 3) return true;
        if(d == 1 and (map[nx][ny] == 3 or map[nx][ny] == 5 or map[nx][ny] == 6)) return true;
        if(d == 2 and (map[nx][ny] == 2 or map[nx][ny] == 6 or map[nx][ny] == 7)) return true;
    } else if(map[x][y] == 7) {
        if(d == 1 or d == 3) return true;
        if(d == 0 and (map[nx][ny] == 3 or map[nx][ny] == 4 or map[nx][ny] == 7)) return true;
        if(d == 2 and (map[nx][ny] == 2 or map[nx][ny] == 6 or map[nx][ny] == 7)) return true;
    }
    return false;
}

int bfs() {
    memset(dist,-1,sizeof(dist));
    queue<Point> q;
    q.push({R,C});
    int ret = 0;
    dist[R][C] = 1;
    while(!q.empty()) {
        int x = q.front().x, y = q.front().y; q.pop();
        if(dist[x][y] <= L) ret++;
        else break;
        for(int i = 0; i < 4; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            if(can_not_move(x,y,nx,ny,i)) continue;
            q.push({nx,ny});
            dist[nx][ny] = dist[x][y]+1;
        }
    }
    return ret;
}

int simulate() {
    return bfs();
}

void input() {
    cin >> N >> M >> R >> C >> L;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> map[i][j];
        }
    }
}

int main() {
    int T;
    cin >> T;
    for(int t = 1; t <= T; t++) {
        input();
        cout << "#" << t << ' ' << simulate() << '\n';
    }
    return 0;
}