이취코테 152p_미로찾기

이것이 취업을 위한 코딩 테스트다 with 파이썬
파이썬 책 보면서 C++로 고쳐풀기
152p_미로찾기

문제 설명

입력을 통해 맵을 구성할 행과 열의 수 n, m을 받는다. 그리고 n*m 형태의, 0(바다)과 1(육지)로 이루어진 맵을 받는다. 각 행은 뉴라인으로 구분되어 있다. 출발지는 좌측최상단, (1, 1)이며 도착지는 우측최하단, (n, m)이다. 플레이어는 바다로는 갈 수 없고, 육지로만 이동할 수 있다. 출발지와 도착지는 무조건 육지이며 출발지에서 도착지까지 갈 수 있는 길이 최소한 한 가지는 무조건 존재한다. 출발지와 도착지를 포함한 최단 이동 칸수를 출력하라.

문제 조건

• 4 ≤ n, m ≤ 200

코드

#include <stdio.h>
#include <queue>

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

static int n = 4, m = 4;

struct pair {
    int x;
    int y;

    pair(int x, int y) {
        this->x = x;
        this->y = y;
    }
};

//char로 할 경우 스페이스도 뉴라인도 다 한개의 char로 취급하기 때문에, 그걸 구별하기 위한 [^\n] 등이 필요함. 
//char로 하면 안되고 무조건 int로 해야한다... 
//오히려 편해짐 괜한 변환 안 해도 됨! 어차피 들어올 때는 한글자씩 오는 거 알고 있으니까 char로 받고 바로 - '0' 해줘서 int화 해주면 간단

//map 배열 간접 참조로 값을 직접 바꾸는데, 이런 방식은 나같은 몽키한테는 더더욱 좋은 습관이 아님. 코테가 아니더라도 복사본을 다루는 습관을 들이자. 
int bfs(int x, int y, int (&map) [200][200]) {
    std::queue<pair> Q;
    Q.push(pair(x, y));
    while (!Q.empty()) {
        pair temp = Q.front();
        Q.pop();

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

            if (nx >= n || ny >= m || nx < 0 || ny < 0) {
                //printf("no way to go\n");
                continue;
            }
            if (map[nx][ny] == 0) {
                //printf("ocean\n");
                continue;
            }
            if (map[nx][ny] == 1) {
                map[nx][ny] = map[temp.x][temp.y] + 1;
                Q.push(pair(nx, ny));
            }
            else {
                //printf("already visited\n");
            }
        }
    }
    return map[n - 1][m - 1];
}

//미로탈출
int main() {
    scanf("%d %d[^\n]", &n, &m);
    int map[200][200];

    for (int i = 0; i < n; ++i) {
        char temp[201];
        scanf("%s", &temp);
        for (int j = 0; j < m; ++j) {
            map[i][j] = temp[j] - '0';
        }
    }

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

    return 0;
}

입력

5 6
101010
111111
000001
111111
111111

출력

10