백준 16954 움직이는 미로 탈출 c++,Kotlin (bfs)

문제 출처 : https://www.acmicpc.net/problem/16954

16954번: 움직이는 미로 탈출

문제

욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다.

이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 이동할 때는 빈 칸으로만 이동할 수 있다.

1초 동안 욱제의 캐릭터가 먼저 이동하고, 그 다음 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다.

욱제의 캐릭터가 가장 오른쪽 윗 칸으로 이동할 수 있는지 없는지 구해보자.

입력

8개 줄에 걸쳐서 체스판의 상태가 주어진다. '.'은 빈 칸, '#'는 벽이다. 가장 왼쪽 아랫칸은 항상 벽이 아니다.

출력

욱제의 캐릭터가 가장 오른쪽 윗 칸에 도착할 수 있으면 1, 없으면 0을 출력한다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

풀이

벽(#)이 움직이는 bfs 문제이다.

매초 움직이는 벽들의 위치만 저장하면 어렵지 않은 문제이고, 움직이는 벽들을

관리하는 방식은 여러 가지다.

 

우선 c++ 풀이는, 그래프를 입력받고, 벽의 위치들을 벡터에 따로 저장했다.

그래프는 딱히 사용하지 않았고, bfs를 돌리며 매초 블럭의 좌표를 저장하는 set을 갱신하였고,

블럭을 피해 욱제가 도착지점(0,7)에 도달하면 return 1 도착하지 못하고 탐색이 끝나면 return 0 하였다.

 

Kotlin 풀이는, 그래프를 입력받아 현재 벽의 위치를 나타냈으며, 다음 벽의 위치를 저장할 새로운 그래프와 현재 벽의 위치를 저장하는 그래프를 매 초마다 갱신해가며 욱제의 위치와 비교하는 방식으로

가장 위에 있는 벽의 높이(i)를 구해서 8-i초만큼 bfs를 돌렸다.

8-i초는 모든 벽이 한 칸씩 떨어져 그래프에서 사라지는 최소 시간이며,

이 시간 동안 욱제가 살아있다면(큐가 비어있지 않다면)  return 1 중간에 큐가 빈다면 return 0 하였다.

 

블럭의 현재 위치와 한 칸 내려온 위치 모두 욱제의 캐릭터와 부딪치면 종료된다는 걸 주의하자.

코드(c++)

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>

using namespace std;
char graph[8][8];
int dir[9][2] = { {0,0}, {1,0},{0,1},{-1,0},{0,-1},{-1,-1},{1,-1},{1,1},{-1,1} };
vector <pair<int, int>> block;
void bfs() {
	
	queue<pair<int, int>> q;
	q.push({ 7,0 });

	while (!q.empty()) {
		int size = q.size();
		set<pair<int, int>> se;
		for (int i = 0; i < block.size(); i++) {
			if (block[i].first <= 7) {
				se.insert({ block[i].first,block[i].second });
				se.insert({ ++block[i].first,block[i].second });
			}
		}
		while(size--) {
			int r = q.front().first;
			int c = q.front().second;
			if (r == 0 && c == 7||se.empty()) {
				cout << 1;
				return;
			}
			q.pop();
			for (int i = 0; i < 9; i++) {
				int nr = r + dir[i][0];
				int nc = c + dir[i][1];
				if (nr >= 0 && nr < 8 && nc >= 0 && nc < 8) {
					if (se.find({ nr,nc }) != se.end()) {
						continue;
					}
					q.push({ nr,nc });
				}
			}
		}
	}
	cout << 0;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			cin >> graph[i][j];
			if (graph[i][j] == '#') {
				block.push_back({ i,j });
			}
		}
	}

	bfs();
	return 0;
}

코드(Kotlin)

import java.util.*

val dir = arrayOf(intArrayOf(0,0), intArrayOf(0,1), intArrayOf(1,0), intArrayOf(0,-1), intArrayOf(-1,0),
    intArrayOf(1,1), intArrayOf(-1,-1), intArrayOf(-1,1),intArrayOf(1,-1))
var graph1 = Array<String>(8,{""})

//이동한 벽을 리턴
fun moveWall() : Array<String>{
    val graph2 = Array<String>(8){""}
    graph2[0] = "........"
    for(i in 1 until 8){
        graph2[i] = graph1[i-1]
    }
    return graph2
}

fun bfs( time : Int) : Int{
    val queue : Queue<Coordi>  = LinkedList<Coordi>()
    queue.add(Coordi(7,0))

    for(t in 0 until time){
        //1초에 한 번씩 벽 움직이기
        val graph2 = moveWall()
        val qSize = queue.size

        for(i in 0 until qSize){
            val (r,c) = queue.poll()
            for(j in 0 until dir.size){
                val nextR = r + dir[j][0]
                val nextC = c + dir[j][1]
                //그래프 안에 있으면
                if(nextR>=0 && nextR <8 && nextC>=0 && nextC<8){
                    //이동한벽과 기존의 벽에 닿지 않으면(queue에 푸시)
                    if(graph1[nextR][nextC]=='#' || graph2[nextR][nextC]=='#')
                        continue
                    queue.add(Coordi(nextR,nextC))
                }
            }
        }
        //time초 동안 살아남지 못하면(큐에 더이상 값이 없으면 0리턴)
        if(queue.isEmpty()){
            return 0
        }
        graph1 = graph2
    }
    //time초 동안 살아남음
    return 1
}

fun main()=with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    var time = 8
    for(i in 0 until 8){
        graph1[i] = br.readLine()
        //벽의 가장 높은 위치 == 벽의 최대 이동 시간
        if(graph1[i].contains('#') && time ==8){
            time = 8-i
        }
    }
    write("${bfs(time)}")
    br.close()
    close()
}

data class Coordi(val r : Int, val c : Int)