boj 3055 탈출

 

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

3055번: 탈출

두 종류의 bfs을 사용하여 해결하였습니다.

하나는 물에 대한 bfs,

하나는 고슴고치에 대한 bfs입니다.

 

[물이 흐르는 조건]

1. 돌을 통과할 수 없다.

2. 비버의 소굴로 이동할 수 없다.

 

[고슴도치가 이동하는 조건]

1. 돌을 통과할 수 없다.

2. 물로 차있는 구역으로 이동할 수 없다.

3. 물이 찰 예정인 칸으로 이동할 수 없다.

 

물이 찰 예정인 칸으로 이동할 수 없다는 말은 물과 고슴도치가 같은 시간에 같은 장소에 갈 수 없다는 것입니다.

 

따라서 물에 대한 bfs로 물이 먼저 흐르게 하고, 그 다음에 고슴도치에 대한 bfs로 고슴도치를 이동시키면 되는 문제입니다.

 

이 과정을 무한반복하여 고슴도치가 비버의 소굴로 이동하면 그 시간을 출력하고,

과정을 반복하던 도중에 고슴도치의 좌표가 들어있는 큐가 비어있으면 탈출에 실패했다는 것이니, "KAKTUS"를 출력합니다.

 

C++ 소스 추가하였습니다.

 

 

[C++]

#include <iostream>
#include <queue>
using namespace std;
 
queue<pair<int, int> > q;
queue<pair<int, int> > wq;
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
bool visit[51][51], wvisit[51][51], chk;
char list[51][51];
int N, M, ex, ey;
 
void waterbfs() {
    int qsize = wq.size();
    while (qsize--) {
        int x = wq.front().first;
        int y = wq.front().second;
        wq.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = x + direct[i][0];
            int ny = y + direct[i][1];
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (wvisit[nx][ny] || list[nx][ny] == 'D' || list[nx][ny] == 'X') continue;
 
            wq.push({ nx,ny });
            wvisit[nx][ny] = true;
            list[nx][ny] = '*';
        }
    }
}
 
void bfs() {
    int qsize = q.size();
    while (qsize--) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = x + direct[i][0];
            int ny = y + direct[i][1];
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (visit[nx][ny] || list[nx][ny] == 'X' || list[nx][ny] == '*') continue;
 
            if (list[nx][ny] == 'D') {
                chk = true;
                return;
            }
            q.push({ nx,ny });
            visit[nx][ny] = true;
        }
    }
}
 
void func() {
    for (int T = 1; ; T++) {
        waterbfs();
        bfs();
 
        if (chk) {
            cout << T << '\n';
            return;
        }
        else if (q.empty()) {
            cout << "KAKTUS\n";
            return;
        }
    }
}
 
void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> list[i][j];
            if (list[i][j] == 'S') {
                q.push({ i,j });
                visit[i][j] = true;
            }
            else if (list[i][j] == 'D') {
                ex = i;
                ey = j;
            }
            else if (list[i][j] == '*') {
                wq.push({ i,j });
                visit[i][j] = true;
            }
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}

 

[Java]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static char list[][] = new char[50][50];
    static boolean qvisit[][] = new boolean[50][50];
    static boolean wvisit[][] = new boolean[50][50];
    static int N, M, ex, ey;
    static Queue<int[]> q = new LinkedList<>();
    static Queue<int[]> w = new LinkedList<>();
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
 
    static void waterbfs() {
        int size = w.size();
        while (size-- > 0) {
            int x=w.peek()[0];
            int y=w.peek()[1];
            w.remove();
            
            for(int i=0; i<4; i++) {
                int nx=x+direct[i][0];
                int ny=y+direct[i][1];
                
                if(nx<0 || ny<0 || nx>=N || ny>=M)
                    continue;
                if(wvisit[nx][ny] || list[nx][ny]=='X' || list[nx][ny]=='D')
                    continue;
                
                w.add(new int[] {nx,ny});
                wvisit[nx][ny]=true;
            }
        }
    }
 
    static boolean bfs() {
        int size=q.size();
        while(size-->0) {
            int x=q.peek()[0];
            int y=q.peek()[1];
            q.remove();
            
            for(int i=0; i<4; i++) {
                int nx=x+direct[i][0];
                int ny=y+direct[i][1];
                
                if(nx<0 || ny<0 || nx>=N || ny>=M)
                    continue;
                if(qvisit[nx][ny] || wvisit[nx][ny] || list[nx][ny]=='X')
                    continue;
                if(nx==ex && ny==ey) 
                    return true;
                
                q.add(new int[] {nx,ny});
                qvisit[nx][ny]=true;
            }
        }
        return false;
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i] = st.nextToken().toCharArray();
            for (int j = 0; j < M; j++) {
                char ch = list[i][j];
                if (ch == 'S') {
                    q.add(new int[] { i, j });
                    qvisit[i][j] = true;
                } else if (ch == '*') {
                    w.add(new int[] { i, j });
                    wvisit[i][j] = true;
                } else if (ch == 'D') {
                    ex = i;
                    ey = j;
                }
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        for(int T=1; ; T++) {
            waterbfs();
            if(bfs()) {
                System.out.println(T);
                break;
            }
            
            if(q.isEmpty()) {
                System.out.println("KAKTUS");
                break;
            }
        }
    }
}