14497 : 주난의 난 - bfs, dfs

https://www.acmicpc.net/problem/14497

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]); 
}