2024 - 09- 24 C++ 코딩테스트 10주완성 D+40

백준 14497 문제 - 주난의 난

 

주난이는 크게 화가 났다.

 

책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다.

 

주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다.

 

‘쿵... 쿵...’

 

주난이는 점프의 파동으로 주변의 모든 친구들을 쓰러뜨리고(?) 누군가 훔쳐간 초코바를 찾으려고 한다.

 

주난이는 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은 친구, *는 주난, #는 범인을 뜻한다.

 

출력

 

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

 

실습코드

 

#include <bits/stdc++.h>

using namespace std;

//1. 변수목록
//교실의 크기의 행과 열의 정보를 담을 정수형 변수 N,M
//주난이와 범인의 위치를 담을 정수형 변수 X1,Y1,X2,Y2
//교실의 정보를 담을 Chracter형 2차원 배열 a
//방문한 곳의 정보를 담을 int형 2차원 배열 visited
//점프한 횟수를 카운트할 정수형 변수 Cnt
//상하좌우로 이동할 좌표를 담은 정수형 배열 dy[4] ={-1,0,1,0},dx[4] = {0,1,0,-1}
//#의 찾음 유무를 표기할 bool형 변수 isFind = false
int N,M,X1,X2,Y1,Y2,cnt;
int visited[504][504];
int dy[4] = {-1,0,1,0};
int dx[4] = {0,1,0,-1};
char a[504][504];
bool isFind = false;

    //2-4-1. void dfs(int y,int x)
    //2-4-1-1. visited[y][x] = 1;
    //2-4-2-1. i = 0 부터 4 미만 반복문
    //2-4-2-1-1. int ny = y + dy[i];
    //2-4-2-1-2. int nx = x + dx[i];
    //2-4-2-1-3. if(ny < 0 || ny >= n || nx < 0 || nx >= m || visited[ny][nx]) continue;
    //2-4-2-1-4. if(a[ny][nx] == '#') isFind = true; return;
    //2-4-2-1-5. else if(a[ny][nx] == '1') return;
    //2-4-1. void dfs(int y,int x) 종료
void dfs(int y,int x)
{
    visited[y][x] = 1;
    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;

        if(a[ny][nx] == '#')
        {
            isFind = true;
            return;
        }
        else if(a[ny][nx] == '1') 
        {
            a[ny][nx] = '0';
            return;
        }
        dfs(ny,nx);
    }
}

int main()
{    
    //2. 알고리즘
    //2-1. N 과 M을 입력받는다.
    //2-2. X1,Y1,X2,Y2 를 입력받는다.
    //2-3. N 만큼 반복문
    //2-3-1. M 만큼 반복문
    //2-3-1-1. a[i][j]안에 원소를 집어넣는다.
    //2-3-1. M 만큼 반복문 종료
    //2-3. N 만큼 반복문 종료
    cin >> N >> M;
    cin >> Y1 >> X1 >> Y2 >> X2;
    for(int i = 0; i < N; i++)
    {
        string str = "";
        cin >> str;
        for(int j =0; j < str.length(); j++)
        {
            a[i][j] = str[j];
        }
    }
    //2-4. while(!isFind) 반복문    
    //2-4-1. dfs(y1-1,x1-1);        
    //2-4-2. if(isFind) cout << cnt; break;
    //2-4-3. else cnt++;
    while(!isFind)
    {
        memset(visited,0,sizeof(visited));
        dfs(Y1-1,X1-1);
        cnt++;

        if(isFind) 
        {
            cout << cnt;
            break;
        }       

    }
          
    return 0;
}

 

예제 출력은 다 통과하였는데,..

 

 

틀렸다고 한다.

 

그래서 강의 실습코드를 보며 이해해본다.

 

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

 

이 코드의 로직은 queue를 무려 두개를 쓴다는 것이다.

 

그리고 y와 x의 좌표를 queue안에 pair 인수를 두어, 따로 담을 수 있지만 

 

여기서는 몫과 나머지로 구분하여 y 와 x의 좌표를 구분하였다.

 

그리고 queue 를 두개씀으로써 먼저 0을 탐색하는 q 와 1을 탐색하는 temp로 나누어 0의 탐색이 끝났을때,

 

Cnt를 증감하고, q 안에 temp값을 집어넣음으로써 다시 탐색한 1의 위치에서 시작할 수 있고,

 

또, 탐색할때마다 visited 배열안에 해당되는 cnt값을 대입시켜준다.

 

이렇게 하면 최종 # 의 위치에 갔을 때, visited[y2][x2] 값을 출력시켜주면 최소 점프값을 구할 수 있다.