반응형
https://www.acmicpc.net/problem/2178
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
풀이
우선 첫 번째는 입력에서 볼드체로 '붙어서'를 강조하는 모습을 볼 수 있습니다.
string으로 받아야겠다는 생각은 했지만, getline으로 받을 생각이었습니다.
이후.. for(auto c : s)를 통해 접근하고자 했지만 이렇게 구현할 경우 index에 접근이 불가하여 미로의 개념이 구현되지 않습니다.
이 부분은 고민하다가 해답을 참고했습니다.
string s[100] 이라 함은 string 객체를 담는 1차원 배열 s를 선언하는 것과 같습니다.
이를 이용하면 마치 char 2차원 배열을 선언하는 것과 같은 효과를 가집니다. 실제 index 접근도 2차원 배열처럼 할 수 있습니다. (적고보니 char 2차원 배열로 구현하면 됬겠네요.)
두 번째 그렇담 최단거리를 어떻게 구할 것인가?입니다. 따로 변수를 선언하여 모든 거리를 저장해놓는 것은 불가능합니다.
조금만 다르게 생각하면?
미로 하나를 더 만들어 각 distance를 누적합 시키면 구하고자 하는 distance를 얻을 수 있습니다.
마침 반드시 0,0에서 시작하여 N-1,M-1에서 끝나는군요.
내 코드
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int vis[101][101];
int dis[101][101];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N, M;
cin >> N >> M;
string s[102]; //102개의 string object를 저장
for (int i = 0; i < N; i++) {
cin >> s[i];
}
queue<pair<int, int>> q;
q.push(make_pair(0, 0));
dis[0][0] = 1; vis[0][0] = 1;
while (!q.empty()) {
pair<int, int> cur = q.front(); q.pop();
for(int dir = 0; dir < 4; dir++) {
int x = cur.X + dx[dir];
int y = cur.Y + dy[dir];
if (x < 0 || y < 0 || x >= N || y >= M) continue;
if (vis[x][y] || s[x][y] == '0') continue;
q.push(make_pair(x, y));
dis[x][y] = dis[cur.X][cur.Y] + 1;
vis[x][y] = 1;
}
}
cout << dis[N-1][M-1];
}
반응형
'Baekjoon' 카테고리의 다른 글
[C++] 7576번 : 토마토 (0) | 2024.03.20 |
---|---|
[C++] 1926번 : 그림 (0) | 2024.03.12 |
[C++] 1021번 : 회전하는 큐 (0) | 2024.03.08 |
[C++] 2164번: 카드2 (0) | 2024.03.07 |
[C++] 10845 : 큐/18258 : 큐2 (1) | 2024.03.06 |