자외선을 피해 가기(BFS)

문제 설명

---

영희는 자외선이 피부에 좋지 않기 때문에 이동 시 자외선에 노출되는 것을 최소한으로 하고 싶어서 가는 길의 자외선 양을 모두 조사하였다.
값이 제 각각이어서 어떤 경로로 가야 좋을지 난감한 영희를 도와주자.
NN 모양의 장소의 모든 길의 자외선 양이 주어지고 영희는 상하좌우 한 칸씩만 이동이 가능하다.
시작점(1,1)에서 도착점(N,N)까지 이동 시 자외선 합의 최소값을 찾아라.
예를 들어 33 장소의 자외선 양이 아래와 같다면 오른쪽처럼 이동하면 8만큼만 노출된다.

입력 설명

---

첫 줄에 N(2≤N≤100)이 들어온다.
그 다음 줄부터 N개의 줄에 각각 N개씩 M(0≤M≤9)이 공백 없이 들어온다.

출력 설명

---

출발점에서 도착점까지 자외선 합의 최소값을 출력한다.

입력 예시

---

3
041
253
620

출력 예시

---

8

#include <stdio.h>
#define MAXN (100)
int N;//가로, 세로 크기
char map[MAXN+10][MAXN+10];//지도정보
 
#define INF (1<<30)
int visited[MAXN+10][MAXN+10];
struct QUE{
    int r, c;
};
struct QUE que[MAXN * MAXN * 100];
int wp, rp;
void push(int r, int c, int t) {
    if (visited[r][c] <= t) return;//이전보다 좋지 않으므로 확산안함
    visited[r][c] = t;//가중치 저장
    que[wp].r = r; que[wp].c = c; wp++;//큐에 저장
}
struct QUE front(void) { 
    return que[rp]; 
}
void pop(void) { 
    rp++; 
}
int empty(void) { 
    return wp == rp; 
}
int BFS(void){
    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};
    for (int i=1; i<=N; i++){
        for (int j=1; j<=N; j++){
            visited[i][j]=INF;
        }
    }
    wp = rp = 0;
    push(1, 1, 0);
    while(!empty()){
        struct QUE cur = front(); pop();
        for (int i=0; i<4; i++){
            int nr = cur.r+dr[i];
            int nc = cur.c+dc[i];
            if (map[nr][nc] == 0) continue;
            push(nr, nc, visited[cur.r][cur.c] + map[nr][nc] - '0');
        }
    }
    return visited[N][N];
}
 
void InputData(void){
    scanf("%d", &N);
    for (int i=1; i<=N; i++){
        scanf("%s", &map[i][1]);
    }
}
 
int main(void){
    int ans = -1;
    InputData();//입력
 
    ans = BFS();//여기서부터 작성
 
    printf("%d\n", ans);//출력
    return 0;
}