문제 풀이 과정을 공유하고자 한다.
문제 출처

1. 문제설명

  • 최대 100 크기의 정사각형 보드가 주어진다.
  • 각 칸은 ., R, D, G 중 하나이며 각각 빈 공간, 로봇의 처음 위치, 장애물의 위치, 목표지점 이다.
  • 말의 움직임은 상, 하, 좌, 우 4방향 중 하나를 선택해서 장애물이나 맨 끝에 부딫힐 때까지 미끄러진다.
    • 이 때 미끄러져 이동하는 것을 한 번의 이동으로 간주한다.



2. 알고리즘 설계

  • BFS 문제
  • 시작점, 목표지점을 미리 기억
    • 목표 지점을 만나면, 걸린 시간 반환
    • 아니라면, -1



3. 로직

  • 미끄러지면 멈추도록 구현
    • if문이 아닌 while문으로 dy[dir], dx[dir] 값을 더해준다.
    for(int dir=0; dir<4; dir++) {
  // 맵의 끝에 도달하거나, 장애물을 만날 때까지 1칸씩 이동시킨다.
  while (ny < y_len && nx < x_len && ny >= 0 && nx >= 0 && board[ny][nx] != 'D') {.....}
}
    • ny, nx 값이 갱신되었는지 체크 필요
      • 갱신되었다면, dy[dir], dx[dir] 값을 각각 빼준다.
      • 갱신된 값은 dy[dir], dx[dir]이 한번 더 더해진 상태이기 때문
    • 방문하지 않은 자리라면 큐에 넣는다.
    if(chk) {
  ny -= dy[dir];
  nx -= dx[dir];

  if(!visited[ny][nx]) {
    // 큐에 넣기
  }
}


4. 전체 코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;
using pii = pair<int, int>;

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

typedef struct {
    int y, x, w;
}pos;

bool visited[100][100];

int solution(vector<string> board) {
    pii src, dest;
    int y_len = board.size();
    int x_len = board[0].size();

    for (int y = 0; y < y_len; y++) {
        for (int x = 0; x < x_len; x++) {
            if (board[y][x] == 'R')
                src = { y, x };
            if (board[y][x] == 'G')
                dest = { y, x };
            visited[y][x] = false;
        }
    }

    queue<pos> q;
    q.push({ src.first, src.second, 0 });
    visited[src.first][src.second] = true;

    while (!q.empty()) {
        pos cur = q.front();
        q.pop();

        if (board[cur.y][cur.x] == 'G')
            return cur.w;

        for (int dir = 0; dir < 4; dir++) {
            int ny = cur.y + dy[dir];
            int nx = cur.x + dx[dir];
            bool chk = false;

            while (ny < y_len && nx < x_len && ny >= 0 && nx >= 0 && board[ny][nx] != 'D') {
                ny += dy[dir];
                nx += dx[dir];
                chk = true;
            }

            if (chk) {
                ny -= dy[dir];
                nx -= dx[dir];
                
                if (!visited[ny][nx]) {
                    q.push({ ny, nx, cur.w + 1 });
                    visited[ny][nx] = true;
                }
            }
        }
    }
    return -1;
}


5. 소감

  • 미끄러지는 걸 어떻게 구현하는지가 관건이라고 생각한다.
  • 다른 부분은 일반적인 BFS 문제와 똑같다.