[C++] 백준 2178 : 미로탐색

#include <iostream>
#include <queue>
using namespace std;

int N, M;
int map[101][101] = {0}; // 미로 입력
bool visited[101][101] = {false}; // 정점 방문 여부
queue<int> x, y, cnt; // 큐 2개 x, y, 칸 수 계산 - 길 탐색할 때 마다 거리 계산

int dx[4] = { 0, 0, -1, 1 }; // 상하좌우 좌표
int dy[4] = { -1, 1, 0, 0 };

bool check(int y, int x){ // y좌표를 먼저 해주는게 좋다고 한다.
    if(y < 1 || y > N || x < 1 || x > M){
        return false; // 좌표 범위 초과하면 갈 수 없음
    } else if(map[y][x] == 0){
        return false; // 벽이 있으면 이동 불가
    } else if(visited[y][x]){
        return false; // 이미 방문 했으면 이동 x
    }
    return true;
}

int main(int argc, char **argv){
    scanf("%d %d",&N,&M);

    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            scanf("%1d", &map[i][j]); // 숫자 1개씩 입력받기
        }
    }

    x.push(1); y.push(1); // 첫 좌표 큐에 집어넣기
    cnt.push(1); // 첫번째 칸
    
    while(!y.empty()){
        int yp = y.front(); y.pop(); // y 좌표 
        int xp = x.front(); x.pop(); // x 좌표 
        int cntp = cnt.front(); cnt.pop(); // 칸 수 세기

        if(visited[yp][xp]){
            continue; // 방문된 노드이면 패스
        } else {
            visited[yp][xp] = true; // 방문 체크
        }

        if(xp == M && yp == N){ // N * M 배열 N은 y, M은 x
            // 도착점 도달
            printf("%d", cntp);
            break;
        }

        // 상하좌우 방문 - else if 사용 x
        if(check(yp + dy[0], xp + dx[0])){ // y 먼저
            x.push(xp + dx[0]); 
            y.push(yp + dy[0]); 
            cnt.push((cntp + 1));
        }
        if(check(yp + dy[1], xp + dx[1])){
            x.push(xp + dx[1]); 
            y.push(yp + dy[1]); 
            cnt.push((cntp + 1));
        }
        if(check(yp + dy[2], xp + dx[2])){
            x.push(xp + dx[2]); 
            y.push(yp + dy[2]); 
            cnt.push((cntp + 1));
        }
        if(check(yp + dy[3], xp + dx[3])){
            x.push(xp + dx[3]); 
            y.push(yp + dy[3]); 
            cnt.push((cntp + 1));
        }
    }

    return 0;
}

bfs 열심히 풀어보려고 공부하면서 푼 문제. 전형적인 bfs 문제라고 볼 수 있다.

이런 미로 문제는 목적지를 찾자마자 최단 경로임을 보장할 수 있으므로 bfs를 사용한다.

bfs, dfs 문제가 너무 싫은게 코드가 너무 길기 때문이다... 다른 분들 코드를 확인해보면 저렇게 2차원 배열을 사용하는 것이 아니라 pair를 사용해서 간단하게 문제를 꾸렸던데 훨씬 깔끔해보인다. 앞으로 이런 형식으로 짜봐야지.

#include <iostream>
#include <queue>
using namespace std;
 
string map[100];
int dis[100][100];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int n,m;
queue<pair<int, int> > q;

void bfs(int x,int y) {
    q.push(make_pair(x, y));
	dis[x][y] = 1;
	while (!q.empty()) {
		x = q.front().first;
		y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < m
			&& dis[nx][ny] == 0 && map[nx][ny] == '1') {
				q.push(make_pair(nx, ny));
				dis[nx][ny] = dis[x][y] + 1;
			}
		}
	}
}
int main(void) {
    cin >> n>> m;
    for (int i = 0; i < n; i++)
		cin >> map[i];
    bfs(0,0);
	cout << dis[n - 1][m - 1]; 
}


출처: https://tooo1.tistory.com/163 [개발자 퉁이리]

실수

전역 변수를 선언해두고 지역 변수를 똑같은 이름으로 또 선언을 해서 값이 전역 변수에 제대로 들어가지 못했다... 로직은 다 짜두고 고작 이것 하나때문에 1시간을 고생했다니 ㅋㅋㅋㅋ 하 좀 더 꼼꼼히 짜야할 필요가 있다.