728x90
🅰️문제주소 : https://www.acmicpc.net/problem/2178
🚩문제
🪡풀이
- 최단경로를 구하는 문제로 BFS를 사용해서 도달한 깊이값을 사용하면 됨.
- 상, 하, 좌, 우 이동이 가능하고 이 이동을 하기위한 값을 미리 저장해 둠.
- 방문한 위치는 depth값을 기록하면서 해당 위치에 도달하기 위한 최솟값을 저장해 둠
☕코드는 아래 숨김
더보기
#include <iostream>
#include <vector>
#include <queue>
#include <string>
static std::vector<std::vector<int>> map;
static std::vector<std::vector<bool>> visited;
static int depth=1;
static int dx[] = { 0, 1, 0 ,-1 };
static int dy[] = { 1, 0, -1, 0 };
static int N, M;
void BFS(int x, int y) {
std::queue<std::pair<int, int>> myQ;
myQ.push(std::make_pair(x, y));
visited[x][y] = true;
while (!myQ.empty()) {
std::pair<int, int> now = myQ.front();
myQ.pop();
for (int i = 0; i < 4; ++i) {
int fir = now.first + dx[i];
int sec = now.second + dy[i];
if (fir >= 0 && sec >= 0 && fir < N && sec < M) { //유효성
if (map[fir][sec] != 0 && visited[fir][sec] == false) { //방문할 필요가 있는지, 방문이미 했는지
visited[fir][sec] = true;
//map[fir][sec]++;
map[fir][sec] = map[now.first][now.second] + 1;
myQ.push(std::make_pair(fir, sec));
}
}
}
}
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
std::cin >> N >> M;
map.resize(N, std::vector<int>(M, 0));
visited.resize(N, std::vector<bool>(M, false));
for (int i = 0; i < N; ++i) {
std::string temp;
std::cin >> temp;
for (int j = 0; j < M; ++j) {
map[i][j] = temp[j] - '0';
}
}
BFS(0,0);
std::cout << map[N - 1][M - 1];
return 0;
}
💡알게 된 것
- 최단경로 구하기는 해당 깊이에 대해 전체 탐색을 끝내게 되는 BFS가 적합함
- 경로가 겹치는 것을 걱정하였으나 이미 최초 해당경로 도달 시 도달 가능한 최솟값이기에 별도의 작업은 필요 없이 방문여부만 체크하면 됨
- 상수로 배열의 길이를 선언할 수 있다면 vector를 안 쓰는 게 더 빠르긴 함
728x90
'운동하는 개발자 > 알고리즘, 코딩테스트' 카테고리의 다른 글
Beakjoon] K번째 수 (백준 1300 코테) - 탐색 (0) | 2023.12.11 |
---|---|
Beakjoon] 트리의 지름 구하기 (백준 1167 코테) - 탐색 (0) | 2023.12.09 |
Beakjoon] DFS와 BFS (백준 1260 코테) - 탐색 (1) | 2023.12.04 |
Beakjoon] 연결 요소의 개수 (백준 11724 코테) - 탐색 (0) | 2023.11.28 |
Beakjoon] 수 정렬하기 3 (백준 10989 코테) - 정렬 (1) | 2023.11.27 |