[백준 2178] 미로 탐색

미로 탐색

문제 설명

첫 입력 값으로 N,M을 입력 받는데 각각 미로의 가로와 세로 값이 된다.
다음 줄에는 0,1로 붙어서 현재 칸을 방문 할 수 있는지의 여부로 입력된다.
(1,1)에서 시작해서 (N,M)에 도달하기 까지의 최적 경로를 구해 출력시킨다.

---

알고리즘

1. 먼저 N,M을 입력받고 각각 0,1을 이어서 입력 받는다.
2. bfs함수로 시작위치인 (0,0)을 전달한다.
3. queue에 pair형태로 x,y좌표를 넣고 visited를 활용하여 방문했다는 의미인 1을 대입한다.
4. queue가 빌때까지 반복하는데, 각각 queue에서 front값(x,y) 즉, 현재 위치를 꺼낸다.
5. 상하좌우 이동한 좌표값을 계산해보고 이동가능하고 방문이 가능한 경우 방문한다.
6. 방문시 visited 를 이용하여 현재 값에서 +1해서 최종 값에 최소 이동경로가 나오도록한다.
7. 반복연산을 위해서 queue에 현재 들어온 노드의 값을 push한다.

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <queue>
#include <utility>
using namespace std;
#define MAX 101

int graph[MAX][MAX];
int visited[MAX][MAX];
int answer = 0;
int N, M;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { -1,1,0,0 };

void bfs(int x, int y)
{
    queue<pair<int, int>>q;
    q.push({ x,y });//첫 값 불러오기
    visited[x][y] = 1;
    while (!q.empty())
    {
        x = q.front().first;//queue의 앞의 값 불러오기 
        y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];//위치이동 반경 계산
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < N && ny < M)//범위내에 해당하는 부분이면 
            {
                if (graph[nx][ny] == 1 && visited[nx][ny] == 0)//이동할 수 있는지 확인하고 방문했는지 확인
                {
                    q.push({ nx,ny });//방문후 큐에 넣기 
                    visited[nx][ny] = visited[x][y] + 1;//이동 수를 구하기 위한 연산
                }
            }
        }
    }
}

int main(void)
{
    cin >> N>>M;
    for (int i = 0; i < N; i++)//연결 관계 입력 받기
    {
        string x;
        cin >> x;
        for (int j = 0; j < M ; j++)
            graph[i][j] = x[j]-'0';
    }

    bfs(0,0);//(0,0)부터 시작

    cout << visited[N - 1][M - 1] << endl;//도착점의 값 출력 

    return 0;
}

 

파이썬 풀이

import sys
from collections import deque

def Input_Data():
    readl = sys.stdin.readline
    N, M = map(int, readl().split())
    graph = []

    for i in range(N):
        graph.append(list(map(int, input())))
    return N, M, graph

d = [(1,0),(0,1),(-1,0),(0,-1)]
def Bfs():
    q = deque()
    q.append((0,0))
    while q:
        x,y = q.popleft()
        for dx, dy in d:
            nx, ny = x+dx, y+dy
            if not (0<=nx<N and 0<=ny<M): continue 
            if maze[nx][ny] == 1: 
                q.append((nx,ny))
                maze[nx][ny] = maze[x][y] + 1
    print(maze[N-1][M-1])

N, M, maze = Input_Data()
Bfs()

문제를 풀면서 느낀점

• DFS를 사용하면 안되는 이유: 재귀 형태라서 시간 초과 됨
• 반복문으로 각각 체크하여 상하좌우 이동의 우선순위를 고려할 필요 없음