문제
입력
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
출력
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
예제
문제 정의
이 문제는 최단 거리를 구하는 것이니 BFS를 이용해 풀었다.
c++을 한 지 얼마 안되어 띄어쓰기 없이 입력되는 값들을 각각 배열에 저장하는 방법을 몰랐는데 scanf, prinf 함수에 대해 알게 되었다.
한 코드 내에서 scanf와 cin을 번갈아가며 쓰는 것은 성능상 좋지 않다
cin과 scanf를 번갈아 호출할 때 성능이 떨어지는 이유는 C++ 표준 입출력 스트림(cin)과 C 표준 입출력 함수(scanf)가 입력 스트림을 처리하는 방식과 버퍼링 방식이 서로 다르기 때문이다.
동기화 문제와 데이터 소비 방식 차이가 복합적으로 작용하여 성능 저하 및 예상치 못한 동작을 초래할 수 있다. 코드 일관성을 위해서라도 한 코드내에 입출력 방식을 하나만 선택해서 쓰는게 좋다
따라서 기존에 공백을 두고 입력 받는 값은
cin >> n >> m대신
scanf("%d %d", &n, &m);이렇게 입력받으면 된다.
101111 과 같이 연속된 숫자값을 각각 입력받고 싶으면
scanf("%1d", &adj[i][j]);와 같이 하나씩 끊어서 변수값에 저장하면 된다.
두 정수 N, M의 범위가 (2 ≤ N, M ≤ 100)이므로 입력 값을 저장한 배열의 최대범위를 넉넉히 adj[104][104]로 정했고 마찬가지로 방문처리 배열도 visited[104][104]로 정했다.
BFS를 사용할 때는 q에 y, x값을 담았다.
adj[i][j]의 값이 1이고 방문하지 않은 것만 차례대로 방문하여
방문할 때마다 visited[i][j]의 값을 이전 방문값에 +1씩 더해 저장했다.
#include<bits/stdc++.h>
using namespace std;
int n, m, cnt, y, x;
int adj[104][104];
int visited[104][104];
const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1, 0, -1};
// bfs
int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%1d", &adj[i][j]);
}
}
queue<pair<int, int>> q;
visited[0][0] = 1;
q.push({0, 0});
while(q.size()) {
tie(y, x) = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny<0 || ny>=n ||nx<0 || nx>=m || adj[ny][nx] == 0) continue;
if (visited[ny][nx]) continue;
visited[ny][nx] = visited[y][x] + 1;
q.push({ny, nx});
}
}
printf("%d", visited[n - 1][m - 1]);
return 0;
}