C - [백준 2178] 미로탐색 (feat. BFS & 최단거리 탐색)

참고 포스트

https://rnasterofmysea.tistory.com/47

C - [Backjoon 1260] DFS와 BFS

 

https://rnasterofmysea.tistory.com/46

[자료구조 & 알고리즘] 그래프 + BFS

 

 

[BOJ 2178] 미로탐색 - BFS를 활용한 최단 거리 탐색

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

 

문제 설명

N×M 크기의 2차원 배열로 표현된 미로가 주어집니다.
미로의 시작점은 (1, 1)이고, 도착점은 (N, M)입니다.
미로에서 1은 이동할 수 있는 칸을, 0은 이동할 수 없는 칸을 의미합니다.
최소 몇 개의 칸을 지나야 시작점에서 도착점으로 이동할 수 있는지를 구하세요.

---

입력 형식

1. 첫째 줄에 미로의 크기 N과 M이 주어집니다. (2 ≤ N, M ≤ 100)
2. 이후 N개의 줄에 M개의 숫자로 이루어진 미로 정보가 주어집니다.
   • 숫자는 공백 없이 입력됩니다.
   • 시작점과 도착점은 항상 이동 가능한 칸(1)입니다.

---

출력 형식

• 첫째 줄에 최소 이동 칸의 수를 출력합니다.
  (시작점과 도착점도 이동 칸 수에 포함됩니다.)

---

예제 입력과 출력

입력 1

4 6
101111
101010
101011
111011

출력 1

15

---

입력 2

2 25
1011011011011011011011011
1111011111011111011111011

출력 2

38

---

Checkpoint

0. 이슈사항 -  동적배열 할당

 

동적배열에 익숙해지고자 전까지 BFS를 구현할 때 동적배열을 사용하여 구현하였습니다.

BFS에서 동적배열을 사용할 수 있는 부분은 크게 3가지가 있다고 판단했습니다.

 

1. 그래프(노드)를 저장할 그래프 배열 (ex: int *graph)

2. 그래프(노드) 방문 여부를 저장할 visited 배열 (ex: int *visited)

3. BFS 탐색을 위한 queue 배열 (ex: int *queue);

 

해당 3가지 항목을 사용자가 입력한 크기 및 최대값에 맞춰 malloc 함수를 이용하여  배열을 할당하였습니다.

 

이번 문제를 풀면서 1, 3번 부분에서 백준 심사 후 runtime(OutofBound) 에러가 발생하는 이슈가 있었습니다.

이번 포스트는 정적 배열로 할당하여 백준 테스트에서 통과하였으나 다음 포스트를 통해 해당 이슈를 해결하여 동적 배열로 구현한 방법에 대해 개시하겠습니다.

1. 기존 알고리즘과의 차이

 

기존에 사용하던 기본적인 BFS 코드(https://rnasterofmysea.tistory.com/47)에 "최단 경로 찾기" 라는 키워드로 방향(x,y)에 대한 처리가 추가된 문제였습니다.

 

즉, 기존의 BFS코드는 탐색 위치를 주어지면 간선이 연결된 연결 요소의 끝까지의 과정을 보여주는 코드였기 때문에 

"그래프 및 노드 생성 -> 간선 연결 -> BFS 알고리즘 실행 (방문하지 않는 노드만 큐에 삽입) -> 결과 출력"  과정이었다면,

 

현재 문제는 해당 요구사항이 추가되었습니다.

 

1. 주어진 지도(m * n 크기의 그래프) 에서 뚫려있는 길( node 값이 1인 것) 즉 유효한 노드만 판단 한 후 BFS를 실행해야 합니다.

 

2. 최적의 경로를 탐색해야하기 때문에 사람이 미로찾기 게임을 하듯이 현재 위치에서 왼쪽으로도 가보고 오른쪽으로도 가봐야하기 때문에 "상하좌우"에 경로에 대해 고려해서 처리해야합니다.

 

즉, 기존 프로세스를 수정을 하게 된다면 다음과 같습니다.

 

"그래프 및 노드 생성 -> BFS 실행(node가 1인 것 중에 방문하지 않는 노드만 큐에 삽입 -> 거리 갱신) -> 결과 출력" 

 

2. 도착점이 항상 최단 거리로 갱신되는 이유

거리 갱신은 다음 식에 의해 이루어집니다:

graph[nx][ny] = graph[x][y] + 1;

• graph[x][y]는 현재 위치까지의 거리입니다.
• 상하좌우로 이동 가능한 다음 위치 (nx, ny)는 현재 거리보다 1만큼 증가한 값으로 갱신됩니다.

처음 방문했을 때가 최단 거리:

• BFS는 큐를 사용하여 노드를 탐색하므로, 도착점 (N-1, M-1)에 처음 도달한 시점이 최단 거리입니다.
• 한 번 방문한 노드(값이 1에서 갱신된 노드)는 다시 방문하지 않기 때문에, graph[N-1][M-1]의 값은 최단 거리로 고정됩니다.

유효한 이동만 처리:

if (nx >= 0 && nx < N && ny >= 0 && ny < M && graph[nx][ny] == 1)

 

• 위 조건에서 graph[nx][ny] == 1은 아직 방문하지 않은 경로만 탐색하게 만듭니다.
• 따라서 BFS는 한 번 방문한 노드에 대해 최단 거리로 갱신된 상태를 유지합니다.

도착점 값 반환

마지막으로 BFS가 끝나면 graph[N-1][M-1]에는 최단 거리가 저장됩니다. 이는 다음 코드에서 반환됩니다:

return graph[N - 1][M - 1];

 

 

예제 설명

4 6
101111
101010
101011
111011

거리 갱신 과정

BFS가 진행되며, graph 배열이 다음과 같이 갱신됩니다:

초기 상태:

1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 1 1 1

1. 시작점 (0, 0)에서 출발:
   • (0, 1)은 벽이므로 탐색 불가.
   • (1, 0)으로 이동, graph[1][0] = 2.
2. 탐색 진행 (BFS 순서대로):
   • 각 경로에서 상하좌우를 탐색하며 거리를 갱신.
   • 도착점 (3, 5)에 처음 도달했을 때 graph[3][5] = 15.

최종 상태:

1 0 9 10 11 12
2 0 8 0 12 0
3 0 7 0 13 14
4 5 6 7 8 15

---

결론

• graph[N-1][M-1]에 최단 거리가 저장되는 이유는 BFS가 탐색 시 한 번 방문한 노드는 최단 거리로 갱신되기 때문입니다.
• 도착점 (N-1, M-1)이 BFS 큐에 처음 들어가는 시점에서의 거리 값이 최단 거리입니다.

---

 

구현코드

/*
https://www.acmicpc.net/problem/2178
[BOJ 2178] 미로탐색
KEYPOINT: x,y 방향
*/


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

// 전역 변수 선언
int graph[100][100];
int queue[10000][2];
int front = 0;
int rear = 0;

// 상하좌우 이동 방향 (x, y)
int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

// 큐 삽입
void enqueue(int x, int y) {
    queue[rear][0] = x;
    queue[rear][1] = y;
    rear++;
}

// 큐 제거
void dequeue(int *x, int *y) {
    *x = queue[front][0];
    *y = queue[front][1];
    front++;
}

// BFS
int bfs(int N, int M) {
    enqueue(0, 0);        // 시작점 삽입
    graph[0][0] = 1;      // 시작점 거리 초기화

    while (front < rear) { // 큐가 비어있지 않을 때
        int x, y;
        dequeue(&x, &y);

        // 상하좌우 탐색
        for (int i = 0; i < 4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];

            // 유효 범위 및 이동 가능 여부 확인
            if (nx >= 0 && nx < N && ny >= 0 && ny < M && graph[nx][ny] == 1) {
                graph[nx][ny] = graph[x][y] + 1;  // 거리 갱신
                enqueue(nx, ny);
            }
        }
    }

    // 도착점 거리 반환
    return graph[N - 1][M - 1];
}

int main() {
    int N, M;
    scanf("%d %d", &N, &M);

    // 미로 입력
    for (int i = 0; i < N; i++) {
        char line[M + 1];
        scanf("%s", line);
        for (int j = 0; j < M; j++) {
            graph[i][j] = line[j] - '0';  // 문자 -> 정수 변환
        }
    }

    // BFS 실행 및 결과 출력
    printf("%d\n", bfs(N, M));
    return 0;
}

---

전역 변수

int graph[100][100];
int queue[10000][2];
int front = 0;
int rear = 0;

• graph[100][100]: 미로 정보를 저장하는 2차원 배열입니다. 최대 크기는 문제 조건에 맞춰 100×100100 으로 설정했습니다.
• queue[10000][2]: BFS에 필요한 큐를 구현하기 위한 배열입니다. 각 원소는 현재 위치의 x와 y 좌표를 나타냅니다.
• front, rear: 큐의 앞과 뒤를 나타내는 변수로, 선형 큐의 상태를 관리합니다.

---

상하좌우 방향 설정

int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

• dir 배열은 BFS 탐색 시 상하좌우 네 방향으로 이동하기 위한 상대 좌표를 정의합니다.

 

---

큐 관련 함수

enqueue

void enqueue(int x, int y) {
    queue[rear][0] = x;
    queue[rear][1] = y;
    rear++;
}

• 큐의 rear에 새로운 좌표 (x,y)(x, y)를 삽입하고, rear 값을 증가시킵니다.

dequeue

void dequeue(int *x, int *y) {
    *x = queue[front][0];
    *y = queue[front][1];
    front++;
}

• 큐의 front에서 좌표 (x,y)(x, y)를 꺼내고, front 값을 증가시킵니다.

 

---

BFS 구현

int bfs(int N, int M) {
    enqueue(0, 0);        // 시작점 삽입
    graph[0][0] = 1;      // 시작점 거리 초기화

    while (front < rear) { // 큐가 비어있지 않을 때
        int x, y;
        dequeue(&x, &y);

        // 상하좌우 탐색
        for (int i = 0; i < 4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];

            // 유효 범위 및 이동 가능 여부 확인
            if (nx >= 0 && nx < N && ny >= 0 && ny < M && graph[nx][ny] == 1) {
                graph[nx][ny] = graph[x][y] + 1;  // 거리 갱신
                enqueue(nx, ny);
            }
        }
    }

    // 도착점 거리 반환
    return graph[N - 1][M - 1];
}

• BFS 알고리즘을 사용하여 최단 거리를 탐색합니다.
• 큐에 시작점 (0,0)(0, 0)을 삽입한 뒤, 큐가 빌 때까지 반복합니다.
• 현재 위치에서 상하좌우 네 방향으로 이동 가능한 위치를 계산한 뒤, 이동 가능하면 큐에 추가하고 거리를 갱신합니다.
• 도착점 (N−1,M−1)(N-1, M-1)에 도달했을 때의 거리를 반환합니다.

---

입력 처리 및 실행

int main() {
    int N, M;
    scanf("%d %d", &N, &M);

    // 미로 입력
    for (int i = 0; i < N; i++) {
        char line[M + 1];
        scanf("%s", line);
        for (int j = 0; j < M; j++) {
            graph[i][j] = line[j] - '0';  // 문자 -> 정수 변환
        }
    }

    // BFS 실행 및 결과 출력
    printf("%d\n", bfs(N, M));
    return 0;
}

1. 입력 처리
   • N×MN \times M 크기의 미로를 입력받아 graph 배열에 저장합니다.
   • 미로는 문자열 형태로 주어지므로 각 문자를 정수로 변환합니다.
2. BFS 실행
   • bfs 함수로 최단 거리를 계산하여 출력합니다.

 

---

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.