[C] 백준 - 2178번: 미로 탐색

6월 5일(월) - 그래프와 순회 (2178번)

2178번: 미로 탐색

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int maze[101][101] = { 0, };
int q[10001][2] = { 0, };

int move_of_x[4] = { -1, 1, 0, 0 };
int move_of_y[4] = { 0, 0, -1, 1 };
int n = 0;
int m = 0;

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

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

        for (int i = 0; i < 4; i++)
        {
            int next_x = x + move_of_x[i];
            int next_y = y + move_of_y[i];

            if (next_x < 1 || next_y < 1 || next_x > n || next_y > m)
            {
                continue;
            }
            if (maze[next_x][next_y] != 1)
            {
                continue;
            }

            maze[next_x][next_y] = maze[x][y] + 1;
            q[rear][0] = next_x;
            q[rear][1] = next_y;
            rear++;
        }
    }

    return maze[n][m];
}

int main(void)
{
    scanf("%d %d", &n, &m);

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

    printf("%d", bfs());

    return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ