(코딩테스트) 백준-14497번 주난의난(bfs)

1) 문제 

 

문제

주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다.

‘쿵... 쿵...’

주난이는 점프의 파동으로 주변의 모든 친구들을 쓰러뜨리고(?) 누군가 훔쳐간 초코바를 찾으려고 한다. 주난이는 N×M크기의 학교 교실 어딘가에서 뛰기 시작했다. 주난이의 파동은 상하좌우 4방향으로 친구들을 쓰러뜨릴(?) 때 까지 계속해서 퍼져나간다. 다르게 표현해서, 한 번의 점프는 한 겹의 친구들을 쓰러뜨린다. 다음의 예를 보자.

1 # 1 0 1 1 1
1 1 0 1 0 0 1
0 0 1 * 1 1 1
1 1 0 1 1 1 1
0 0 1 1 0 0 1

 

주난이를 뜻하는 *은 (3, 4)에 있고, 초코바를 가진 학생 #는 (1, 2)에 있다. 0은 장애물이 없는 빈 공간임을 뜻하고, 1은 친구들이 서있음을 의미한다. 다음은 주난이의 점프에 따른 생존(?) 학생들의 변화이다.

 

1 # 1 0 1 1 1
1 1 0 0 0 0 1
0 0 0 * 0 1 1
1 1 0 0 1 1 1
0 0 1 1 0 0 1

 

1 # 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 * 0 0 1
0 0 0 0 0 1 1
0 0 0 0 0 0 1

 

0 X 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 * 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0

 

위의 예시에서 주난이는 3번의 점프 만에 초코바를 훔쳐간 범인을 찾아낼 수 있다!

주난이를 빨리 멈춰야 교실의 안녕을 도모할 수 있다. 주난이에게 최소 점프 횟수를 알려줘서 교실을 지키자.

입력

첫째 줄에 주난이가 위치한 교실의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 300)

둘째 줄에 주난이의 위치 x1, y1과 범인의 위치 x2, y2가 주어진다. (1 ≤ x1, x2 ≤ N, 1 ≤ y1, y2 ≤ M)

이후 N×M 크기의 교실 정보가 주어진다. 0은 빈 공간, 1은 친구, *는 주난, #는 범인을 뜻한다.

출력

 

주난이가 범인을 잡기 위해 최소 몇 번의 점프를 해야 하는지 출력한다.

 

예제 입력 1

5 7
3 4 1 2
1#10111
1101001
001*111
1101111
0011001

예제 출력 1 

3

 

2) 풀이

2.1)  입력조건

- 최대 탐색 범위는 300+300번으로 하나씩 탐색 가능

- dfs/bfs로 문제 풀이 

2.2)  풀이과정 

- 케이스 별로 담는 큐가 다르다.

- 0일 때는 계속 진행, 1일때는 멈춤

- 이를 코드로 생각 하면 0일때는 q1에 담아 q1을 순회하고, 1일때는 q2에 담아 순회

- q1을 다 순회하면 q2를 새로운 q1으로 설정하여 순회 시작

2.3)  코드

#include <bits/stdc++.h>
using namespace std;

int n, m, visited[301][301], jy, jx, ty, tx;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
char a[301][301];

int main()
{
    cin >> n >> m;
    cin >> jy >> jx >> ty >> tx;
    jy--;
    jx--;
    ty--;
    tx--;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> a[i][j];
        }
    }

    queue<pair<int, int>> q;
    q.push({jy, jx});
    visited[jy][jx] = 1;
    int cnt = 0;

    while (a[ty][tx] != '0')
    {
        cnt++;
        queue<pair<int, int>> temp;
        while (q.size())
        {
            int y, x;
            tie(y, x) = q.front();
            q.pop();
            for (int i = 0; i < 4; i++)
            {
                int ny = y + dy[i];
                int nx = x + dx[i];
                if (ny < 0 || nx < 0 || ny >= n || nx >= m || visited[ny][nx])
                    continue;
                visited[ny][nx] = cnt;
                if (a[ny][nx] != '0')
                {
                    a[ny][nx] = '0';
                    temp.push({ny, nx});
                }
                else
                {
                    q.push({ny, nx});
                }
            }
        }
        q = temp;
    }
    cout << visited[ty][tx];
}

3) 해설

3.1)  조건

- 0일 때는 계속 해서 탐색, 1일때는 멈춤! 

3.2)  사용된 알고리즘

- 이중 q담기

while (도둑놈의 위치가 0입니까?){
	탐색 횟수 증가;
    임시 queue temp 생성;
    while (원래 q가 비었음?){
    	큐에서 하나 꺼내;
        방문처리;
        if 맵에서 벗어났거나, 방문햇던 데면 컨티뉴;
        다음 포인트가 0이 아니다 -> 멈추고 temp에 넣어;
        다음 포인트가 0이다 -> 계속 탐색해야하니까 q에 넣어
        }
        사방에서 멈췄으니까 
        이제 q = temp로 해서 다시 순회시작
   }

 

3.3)  완성된 코드

- 2차원 좌표값은 int 하나로 표현하기 
- int value = (Y좌표) * (조건에 주어진 범위보다 큰값) + (X좌표)
- 사용할때는 
  - > Y좌표 = value / (조건에 주어진 범위보다 큰값)
  - > X좌표 = value % (조건에 주어진 범위보다 큰값)

#include <stdio.h>
#include<algorithm>
#include<queue>
using namespace std; 
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]); 
    }  
    q.push(1000 * y1 + x1);
    visited[y1][x1] = 1; 
    int cnt = 0; 
    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);
                }
                else q.push(1000 * ny + nx); 
            }
        }
        q = temp;  
    }
    printf("%d\n", visited[y2][x2]); 
}

 

3.4)  감상

- queue를 하나만 써야한다는 생각을 버리자

- 주난이는 무섭다