[BFS/DFS] C 프로그래머스 리코쳇 로봇 풀이

문제

• 리코쳇 로봇

풀이 과정

• 핵심 조건은 이동 시 미끄러져 장애물 전에 멈춘다는 것
  • 상하좌우를 1개씩이 아닌 D를 만나기 전까지 증가
  • 이 후 D일 때 멈추므로 한 번씩 빼준 뒤 방문배열 통해서 중복 체크 하는 로직 넣으면 됨
• 나머지는 일반 bfs문제와 같다

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

#define MAX 101

typedef struct Que {
    int x;
    int y;
    int dist;
} Q;

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

char map[MAX][MAX];
int visit[MAX][MAX];
int rows;
int cols;

Q que[MAX*MAX];
int front;
int rear;

void enqueue(int x, int y, int dist) {
    que[rear].x = x;
    que[rear].y = y;
    que[rear].dist = dist;
    rear++;
}

Q dequeue() {
    return que[front++];
}

int bfs() {
    while (front < rear) {
        Q cur = dequeue();
        
        if (map[cur.x][cur.y] == 'G') return cur.dist;
        
        for (int i=0; i<4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            
            while (nx >= 0 && nx < rows && ny >= 0 && ny < cols && 
                   map[nx][ny] != 'D') {
                nx += dx[i];
                ny += dy[i];
            }
            
            nx -= dx[i];
            ny -= dy[i];
            
            if (visit[nx][ny] == 0) {
                enqueue(nx, ny, cur.dist+1);
                visit[nx][ny] = 1;
            }
        }
    }
    return -1;
}

int solution(const char* board[], size_t board_len) {
    front = rear = 0;
    memset(visit, 0, sizeof(visit));
    
    rows = board_len;
    cols = strlen(board[0]);
    for (int i=0; i<rows; i++) {
        strcpy(map[i], board[i]);
    }
    
    for (int i=0; i<rows; i++) {
        for (int j=0; j<cols; j++) {
            if (map[i][j] == 'R') {
                enqueue(i, j, 0);
                visit[i][j] = 1;
            }
        }
    }
    
    return bfs();
}