Machineboy空
14497 : 주난의 난 - bfs, dfs 본문
https://www.acmicpc.net/problem/14497
문제요약
한 번의 점프 시, 벽에 닿을 때까지 진동이 상하좌우로 퍼져나간다.
범인을 찾을 때까지 몇 번의 점프를 해야하는가.
난이도
Gold 4
풀이 포인트
- bfs 응용
- 문제 잘읽기
REVIEW
단순한 dfs 문제겠거니 하면서 풀이 시작했는데,
계속 segment fault에 부딪혔다.
정답률이 53%라, 나도 풀 수 있겠거니하고 계속해서 도전하다가 실패했다.
난이도를 확인하니 과연 gold 4였다.
모범 답안은 bfs로 푸는데, dfs로도 할 수 있을 것 같아서 도전해보려다 접었다.
다시 풀땐 꼭 dfs로 해보기.
기존 bfs가 현재 좌표 기준 상하좌우의 depth별로 queue에 넣고 탐색 후 빼는 방법으로 구현한다면,
이 문제에서는 queue를 두 개 활용하여 0이면 temp에, 1이면 q에 넣어
서브 루프와, 메인 루프를 나누어 돌린다.
모범 코드를 이해는 했으나, 아직 체득해서 쓰라고 하면 못할 것 같다..
계속 연마!
CODE
#include <stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
// 0을 만나면 계속 탐색, 1 만나면 멈추기
// 기존의 bfs에 queue를 두 개 사용
char a[301][301];
int n, m, x1, y1, x2, y2;
typedef pair<int, int> pii;
int visited[301][301];
const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1, 0, -1};
int ret;
queue<int> q;
int main(){
scanf("%d %d", &n, &m);
scanf("%d %d %d %d", &y1, &x1, &y2, &x2);
y1--, x1--, y2--, x2--;
for(int i = 0; i < n; i++){
scanf("%s", a[i]);
}
//2차원 좌표 하나로 받는 법
q.push(1000 * y1 + x1);
visited[y1][x1] = 1;
int cnt = 0;
// '1'과 '#'를 구분해주지 않아도 되는 이유는?
// 여기서 #을 거르기 때문?
while(a[y2][x2] != '0'){
cnt++;
queue<int> temp;
while(q.size()){
int y = q.front() / 1000;
int x = q.front() % 1000;
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 || visited[ny][nx]) continue;
visited[ny][nx] = cnt;
if(a[ny][nx] != '0'){
a[ny][nx] = '0';
temp.push(1000 * ny + nx);
// 1 만나기 전 0들은 temp에 넣고
// 1 만나면 q에 넣고
}
else q.push(1000 * ny + nx);
}
}
q = temp;
}
printf("%d\n", visited[y2][x2]);
}
'Computer > Coding Test' 카테고리의 다른 글
1931: 회의실 배정 - 그리디 (0) | 2024.06.07 |
---|---|
1987 : 알파벳 - DFS, BFS (0) | 2024.04.02 |
14620 : 꽃길 - dfs (0) | 2024.03.28 |
1189: 컴백홈 - DFS (0) | 2024.03.22 |
17071: 숨바꼭질 5 (0) | 2024.03.20 |