(C++) - 백준(BOJ) 1726 : 로봇

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

1726번: 로봇

bfs 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

방향 배열 dr, dc, 공장 정보 factory, 특정 구역의 움직임 횟수를 저장할 moved, 구조체 Robot, 시작 점 도착점 start, dest를 선언 후 적절히 입력받습니다.

편의상 방향을 바꿔주는 것이 구현에 편합니다. 동,남,서,북 순으로 index를 +1, -1하기 편하게 일차원 방향 배열의 값들을 배치했습니다.

📔 풀이과정

어느 방향에서 목적지로 도착할지 알 수 없어 dp로 풀기 어렵습니다. cost가 없기 때문에 pq를 사용할 필요가 없습니다. 따라서 제일 적은 움직임으로 i행, j열로 도착하는 bfs를 수행합니다.*편의상 n을 행, m을 열로 저장했습니다. 문제에서는 반대입니다.*같은 방향으로 1, 2, 3갈 때 벽을 뛰어넘을 수 없으므로 순서대로 for loop를 수행하며 벽을 발견하면 바로 탈출해야 합니다.*i,j에 d방향으로 배열에 값이 저장되는 순간이 로봇이 최소로 도착한다의 의미입니다. 도착하자마자 저장된 배열의 값을 반환합니다.

📔 정답출력

bfs함수 결과를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
int dr[] = {0, -1, 0, 1}; //동 남 서 북
int dc[] = {-1, 0, 1, 0};
int factory[101][101], moved[101][101][5], n, m;
struct Robot{ int r, c, d; };
Robot start, dest;

int bfs(){
  queue <Robot> q;
  moved[start.r][start.c][start.d] = 0;
  q.push({start.r, start.c, start.d});
  while(!q.empty()){
    int r = q.front().r;
    int c = q.front().c;
    int d = q.front().d;
    q.pop();
    if(r == dest.r && c == dest.c && d == dest.d) return moved[r][c][d];
    for(int i = 1; i <= 3; i++){
      int nr = r + dr[d]*i;
      int nc = c + dc[d]*i;
      if(1 > nr || nr > n || 1 > nc || nc > m) continue;
      if(factory[nr][nc]) break;
      if(moved[nr][nc][d] >= 0) continue;
      moved[nr][nc][d] = moved[r][c][d] + 1;
      q.push({nr, nc, d});
    }

    int nd = (d + 1) % 4;
    if(moved[r][c][nd] == -1){
      moved[r][c][nd] = moved[r][c][d] + 1;
      q.push({r, c, nd});
    }
    nd = (d + 3) % 4;
    if(moved[r][c][nd] == -1){
      moved[r][c][nd] = moved[r][c][d] + 1;
      q.push({r, c, nd});
    }
  }
  return 0;
}

void setDirection(Robot &rob){
  if(rob.d == 1) rob.d = 2;
  else if(rob.d == 2) rob.d = 0; 
  else if(rob.d == 3) rob.d = 3; 
  else rob.d = 1;
}

int main(){
  memset(moved, -1, sizeof(moved));
  cin >> n >> m;
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
      cin >> factory[i][j];

  cin >> start.r >> start.c >> start.d;
  cin >> dest.r >> dest.c >> dest.d;

  setDirection(start);
  setDirection(dest);

  cout << bfs();
}

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.