티스토리 뷰
1.문제
https://www.acmicpc.net/problem/2178
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
2. 문제 풀이
#include <iostream>
#include <bits/stdc++.h>
#pragma warning (disable:4996)
#define X first
#define Y second
using namespace std;
string board[105];
int dist[105][105];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int n, m;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> board[i];
for (int i = 0; i < n; i++) fill(dist[i], dist[i] + m, -1);
queue<pair<int, int>> Q;
Q.push({ 0,0 });
dist[0][0] = 0;
while (!Q.empty()) {
auto cur = Q.front(); Q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (board[nx][ny] == '0' || dist[nx][ny] >= 0) continue;
dist[nx][ny] = dist[cur.X][cur.Y] + 1;
Q.push({ nx,ny });
}
}
cout << dist[n - 1][m - 1] + 1;
}
3. 문제 평가 및 해설
BFS 단골 문제인 미로 찾기 문제이다. 기존의 Flood fill 알고리즘에서 visit 배열 대신 distance 배열을 만들어주는게 포인트이다.
이 때, distance 배열은 -1로 초기화해야한다. 이유는 시작 위치의 거리가 0이라고 생각해야하고, 벽과 같은 갈 수 없는 장소는 가지 못함을 표기하기 위해서 -1로 초기화해야하기 때문이다.
Flood fill 알고리즘과 전체적인 흐름은 비슷하다. 문제 풀이는 다음과 같다.
1. distance 배열을 -1로 초기화 한다.
2. 시작 위치(0,0)를 큐에 넣어준다.
3. 시작 위치를 기준으로 상하좌우를 탐색한다. 이 때, 벽이거나 방문한 노드 또는 해당 위치가 맵의 범위를 초과한다면 건너뛰어줘야 한다.
4. distance 배열을 업데이트한다. 현재의 distance에서 1을 더해주면, 해당 위치의 거리이다. 왜냐하면 해당 위치에서 상하좌우까지의 거리는 1이기 때문이다.
5. 3번/ 4번을 큐가 비워질 때까지 반복한다.
번외로 첫풀이에, 다음과 같이 풀었는데, "맞았습니다"라고 떠서 찝찝했다.
#include <iostream>
#include <bits/stdc++.h>
#pragma warning (disable:4996)
#define X first
#define Y second
using namespace std;
string board[105];
int dist[105][105];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int n, m;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> board[i];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] == '0' || dist[i][j] > 0) continue;
queue<pair<int, int>> Q;
Q.push({ i,j });
while (!Q.empty()) {
auto cur = Q.front(); Q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (board[nx][ny] == '0' || dist[nx][ny] > 0) continue;
Q.push({ nx,ny });
dist[nx][ny] = dist[cur.X][cur.Y] + 1;
}
}
}
}
cout << dist[n - 1][m - 1] + 1;
}
Flood fill 알고리즘에 꽂혀있어서 맵을 반복하면서 BFS를 진행했다.
코드의 문제점은
1. distance 배열을 -1로 초기화 안했고
2. 시작위치가 있는데, 굳이 2중 for문으로 탐색했다.
물론, continue를 써서 시간복잡도도 해결했지만 시작위치가 있다면, 이렇게 푸는 방식은 효율적이지 못하다..
운이 좋게 맞은 case인 것 같다. BFS와 관련된 문제를 많이 풀어봐야겠다.
'백준(C++) > 문제풀이' 카테고리의 다른 글
[백준 4179/C++] 불! (0) | 2023.08.04 |
---|---|
[백준 7576/C++] 토마토 (0) | 2023.07.29 |
[백준 1926/C++] 그림 (0) | 2023.07.28 |
[백준 3986/C++] 좋은 단어 (0) | 2023.07.21 |
[백준 4949/C++] 균형잡힌 세상 (0) | 2023.07.19 |
- Total
- Today
- Yesterday
- android studio
- 코딩테스트
- C++ #알고리즘 #연결리스트
- AAR metadata 에러
- 백준 3986
- constraint missing 오류
- 백준 4179
- #include<bits/stdc++.h> # Visual studio #코딩테스트 꿀팁 #알고리즘 풀이
- 알고리즘 #백준 3273 #C++
- 백준 #알고리즘 풀이 #백준 1475
- 백준 1697
- 백준 1021
- 백준 7569
- C++ #알고리즘 #코딩테스트
- 알고리즘 풀이
- 안드로이드 스튜디오
- 백준 7576
- 백준 4949
- 백준 5430
- 알고리즘 정리
- 알고리즘
- 백준1158
- 백준 2164
- 백준 2493
- 문제 유형
- 백준 2178
- C++
- 코테
- ViewBinding
- Render Problem
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |