
개요
항상 완전 탐색 문제가 모두 bfs 및 dfs로 풀 수 있는 것은 아닙니다. 이 문제는 bfs로 풀어야 하는 문제입니다.
접근 방법
(1,1) 좌표에서 (N,M) 좌표까지 이동하기 위해 필요한 최소 칸 수를 구해야 합니다.
BFS 또는 DFS 기법을 통해 탐색을 해야 합니다.
일반적인 완전 탐색의 조건은 아래와 같습니다.
- 문제 요구사항에 만족하는 범위에 위치
- 좌표의 값이 0이 아니며
- 처음 방문
문제 특성 상 (1,1)좌표를 제외하고 좌표의 값이 1인 경우일 때, 무조건 처음 방문하는 좌표입니다. 따라서 처음 방문하는 좌표를 계속 탐색하며 값을 갱신해 주면 됩니다.
솔루션
#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;
int N, M;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
vector <vector <int> > MAP(101, vector<int>(101, 0));
vector <vector <bool> > VISITED(101, vector<bool>(101, false));
void bfs() {
queue <pair<int, int> > Q;
Q.push(make_pair(0 ,0));
VISITED[0][0] = true;
while(!Q.empty()) {
int x = Q.front().first;
int y = Q.front().second;
Q.pop();
for(int i=0; i<4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || nx >= N || ny < 0 || ny >= M) {
continue;
}
if(MAP[nx][ny] == 0 || VISITED[nx][ny]) {
continue;
}
VISITED[nx][ny] = true;
MAP[nx][ny] = MAP[x][y] + 1;
Q.push(make_pair(nx, ny));
}
}
}
int main() {
cin >> N >> M;
for(int n=0; n<N; n++) {
string str; cin >> str;
for(int m=0; m<M; m++) {
MAP[n][m] = str[m] - '0';
}
}
bfs();
cout << MAP[N-1][M-1];
return 0;
}
참고 자료
https://www.acmicpc.net/problem/2178
https://www.acmicpc.net/board/view/25832
[백준] 2178번: 미로 탐색 <75>
직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 최단거리를 구...
blog.naver.com
[백준 2178번 / C++] 미로 탐색
해당 문제를 bfs() 를 활용해서 풀었다. bfs나 dfs 를 어느정도 활용 할 줄 아시는 분이라면 쉽게 풀수 있을 것이다. 항상 (1,1) 에서 출발하여 해당 지점부터 map 의 1로 저장되어 있는 부분을 지나가
baebalja.tistory.com
'컴퓨터공학 & 정보통신 > 알고리즘 문제 풀이' 카테고리의 다른 글
[알고리즘/수학] 나머지 분배 법칙 (1) | 2024.08.23 |
---|---|
[백준] 1946 신입 사원 c++ (0) | 2024.08.11 |
[백준] 17485 진우의 달 여행 (Large) c++ (0) | 2023.11.17 |
[백준] 11052 카드 구매하기 c++ 문제 풀이 (0) | 2023.08.26 |
[백준] 1463 1로 만들기 (0) | 2023.07.07 |