[백준] 2178번 미로 탐색(python,c++)

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

2178번: 미로 탐색

 

---

SOLUTION CODE

# PYTHON

from collections import deque

dy = (0, 1, 0, -1)
dx = (1, 0 ,-1, 0)

N,M = map(int,input().split())
board = [input() for _ in range(N)] # String으로 받음

def is_valid_coord(y,x):
    return 0<=y<N and 0<=x<M

def bfs():
    chk = [[False] * M for _ in range(N)]
    chk[0][0] = True
    dq = deque()
    dq.append(0,0,1)
    while dq:
        y, x, d= dq.popleft()
        
        if y == N-1 and x = M -1:
            return d
        
        nd = d+1
        for k in range(4):
            ny = y + dy[k]
            nx = x + dx[k]
            if is_valid_cood(ny,nx) and board[ny][nx] == '1' and not chk[ny][nx]:
                chk[ny][nx] = True
                dq.append((ny,nx,nd))


bfs()

# C++

#include <iostream>
#include <queue>
#define MAX 101

using namespace std;

int N,M;
int maze[MAX][MAX];
int visited[MAX][MAX];
int dist[MAX][MAX]; // 이동칸 수

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

queue<pair<int,int>> q;

void bfs(int start_x,int start_y){
    visited[start_x][start_y] = 1; //방문체크
    q.push(make_pair(start_x,start_y));
    dist[start_x][start_y]++;
    
    // 모든 좌표를 탐색할 때까지 반복
    while(!q.empty()){
        
        // queue 첫번째 좌표 꺼내기
        int x = q.front().first;
        int y = q.front().second;
        
        q.pop();
        
        for(int i=0;i<4;++i){
            
            int y_new = y+dy[i];
            int x_new = x+dx[i];
            
            // 유효범위+방문X+이동가능확인
            if((0<=x_new && x_new <N) && (0<=y_new && y_new < M)
            && !visited[x_new][y_new] && maze[x_new][y_new] ==1 )
            {
                visited[x_new][y_new] = 1; // 방문체크
                q.push(make_pair(x_new,y_new)); // 큐에 삽입
                dist[x_new][y_new] = dist[x][y] +1;
                
            }
        }
    }
}

int main() {
    cin >> N, M; // 미로크기
    
    for(int i=0;i<N;i++){
        String row;
        cin >> row; // ex_110111...
        
        for(int j=0;j<M;++j){ // 행별 좌표저장
            maze[i][j] = row[j] - '0'; //문자->숫자 변환
        }
    }
    
    bfs(0,0);
    
    cout<<dist[N-1][M-1];
}