[Baekjoon]백준 2178 미로 탐색(실버 1) - Python/C/C++

문제설명

예제

해당 문제를 살펴보면 서로 인접한 이동가능한 칸으로 이동하여 제일 왼쪽 위(0,0)에서

제일 오른쪽 아래(n-1, m-1)로 이동하는 가장 적은 경우의 수를 출력하는 문제이다

해당 문제의 경우 이전 문제에서 자주 사용하였던 DFS가 아니라 BFS를 사용하여 문제를 해결해야한다

DFS는 한 방향으로 끝까지 탐색한 후 다른 경로를 찾아보기 때문에 

최단 경로를 찾아야하는 해당 문제에서는 BFS를 사용해야한다

 

그에 맞게 적절히 코드를 수정하면 다음과 같다

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def bfs(x, y):
    queue = deque([(x, y)])
    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or nx >= row or ny < 0 or ny >= col:
                continue
            
            if maze[nx][ny] == 1:
                maze[nx][ny] = maze[x][y] + 1
                queue.append((nx, ny))
                
    return maze[row-1][col-1]

BFS의 경우 큐로 표현하는 것이 편리하다

큐에 탐색할 위치가 남아있는 동안 계속 반복하게 되며 다음에 이동할 위치를 계속해서 탐색한다

이후 이동가능한 길이라면 현재 위치까지의 거리에 1을 더한 값을 새로운 위치에 기록한다

해당 과정을 반복하다보면 [row-1][col-1]의 위치에는 최단거리가 저장된다

해당 문제는 각각의 수가 붙어서 입력으로 주어지기 때문에 input().strip()을 사용하여 입력받고 저장하면 된다

import sys
from collections import deque
input = sys.stdin.readline

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def bfs(x, y):
    queue = deque([(x, y)])
    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or nx >= row or ny < 0 or ny >= col:
                continue
            
            if maze[nx][ny] == 1:
                maze[nx][ny] = maze[x][y] + 1
                queue.append((nx, ny))
                
    return maze[row-1][col-1]

row, col = map(int, input().split())
maze = []
for _ in range(row):
    maze.append(list(map(int, input().strip())))
print(bfs(0, 0))

이번에도 이전 문제들처럼 C/C++로 변환하여 다시 작성해보았다

파이썬에는 collections 모듈의 deque 클래스가 존재하지만, C언어에는 해당 기능을 수행하는

라이브러리나 함수가 존재하지 않기 때문에 직접 큐를 구현해주어야한다

밑의 코드에서는 배열과 두개의 정수(front, rear)를 통해 직접 선형 큐를 구현해주었다

queue[i]에는 (x, y) 좌표 한 쌍이 저장되며 rear가 가리키는 위치에 새로운 좌표를 저장하고,

index를 증가시켜 한 칸 뒤로 밀림을 표현할 수 있다

반대로 front는 데이터를 꺼낼때 사용하게 되는데, front를 1 증가시켜 맨 앞이 바뀌었음을 뜻하게 된다

#include <stdio.h>

#define MAX_SIZE 100

int maze[MAX_SIZE][MAX_SIZE];
int queue[MAX_SIZE * MAX_SIZE][2];
int row, col;

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

int bfs() {
    int front = 0;
    int rear = 0;
    queue[front][0] = 0;
    queue[front][1] = 0;
    rear++;

    while(front < rear) {
        int x = queue[front][0];
        int y = queue[front][1];
        front++;

        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= row || ny < 0 || ny >= col) {
                continue;
            }
            if (maze[nx][ny] == 1) {
                maze[nx][ny] = maze[x][y] + 1;
                queue[rear][0] = nx;
                queue[rear][1] = ny;
                rear++;
            }
        }
    }
    return maze[row-1][col-1];
}

int main() {
    scanf("%d %d", &row, &col);

    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            scanf("%1d", &maze[i][j]);
        }
    }

    printf("%d\n", bfs());
}

C++에는 queue 라이브러리가 존재하기 때문에, 이를 활용하여 코드를 작성하면 다음과 같다

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

using namespace std;

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

int bfs(int row, int col, vector<vector<int>>& maze) {
    queue<pair<int, int>> q;

    q.push({0, 0});

    while (!q.empty()) {
        pair<int, int> current = q.front();
        q.pop();

        int x = current.first;
        int y = current.second;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || nx >= row || ny < 0 || ny >= col) {
                continue;
            }

            if (maze[nx][ny] == 1) {
                maze[nx][ny] = maze[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    return maze[row-1][col-1];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int row, col;
    cin >> row >> col;

    vector<vector<int>> maze(row, vector<int>(col));

    for (int i = 0; i < row; i++) {
        string row_str;
        cin >> row_str;
        for (int j = 0; j < col; j++) {
            maze[i][j] = row_str[j] - '0';
        }
    }

    cout << bfs(row, col, maze) << endl;

    return 0;
}