백준 21922 학부 연구생 민상 c++,Kotlin (bfs)

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

21922번: 학부 연구생 민상

문제

학부 연구생으로 새로 연구실에 들어온 민상이는 사용할 자리를 정하려고 한다.

연구실은 격자 모양으로 되어있고 에어컨에서 바람이 상,하,좌,우 4$4$방향으로 분다. 물론 에어컨이 위치한 곳에도 바람이 분다.

민상이는 더위를 많이 타서 에어컨 바람이 지나가는 곳 중 하나를 선택하여 앉으려고 한다.

연구실에는 다양한 물건들이 있어 바람의 방향을 바꾼다.

연구실에 있는 물건의 종류는 총 4가지가 있다. 아래 화살표의 의미는 바람이 각 물건에서 바람의 이동을 표시한 것이다.

연구실 어디든 민상이가 앉을 수 있는 자리이다. 즉 에어컨이 위치한 자리와 물건이 있는 자리 모두 앉을 수 있다.

민상이가 원하는 자리는 몇 개 있는지 계산해주자.

입력

출력

민상이가 원하는 자리의 개수를 출력한다.

알고리즘 분류

• 구현
• 시뮬레이션

풀이

그래프에서 노드의 이동을 예쁘게 짜려면 생각을 좀 해봐야 하고 나머지 풀이는 어렵지 않다.

1. 에어컨의 위치를 입력받아, 에어컨의 4방향을 큐에 push한다.

2. 노드의 재방문은 같은 방향으로 들어왔을 땐 다시 방문할 필요 없고, 다른 방향으로 들어왔을 땐 방문해야 한다. 
   visited[4][][] 3차원 배열로 방향별로 방문 표시를 구현할 수 있다.

3. 1,2블럭을 만났을 때 물건과 수직 방향이라면 continue, 9(에어컨)을 만나도 continue

4. 2차원 배열에 바람이 지난 경로를 중복되지 않게 저장함으로써, 바람이 지나간 경로의 수를 알 수 있다.

 

본인은 4번 과정을 set에 저장하여 중복을 없앴는데, set에 좌표를 add하는 게 2차원 배열에 값을 저장하고 합을 구하는 것보다 느리다는 것을 알게 되었다.... 4시간 만에... 시간 초과 나서 다른 거 다 고쳤는데 결국엔 마지막에 고친 set이 느리다는 게 문제였다.

 

코드(c++)

#include <iostream>
#include <vector>
#include <queue>

#define MAX 2000	
using namespace std;
int n, m;
int graph[MAX][MAX];
bool visited[4][MAX][MAX];
queue<pair<pair<int, int>, int>> q;
int answer[MAX][MAX];
//1<= n<=2000 1<=m<=2000 n!=m
//에어컨 0~50개

//상우하좌
int mov[4][2] = { {-1,0}, {0,1},{1,0} ,{0,-1} };

void bfs() {
	
	while (!q.empty()) {
		int dir = q.front().second;
		int nR = q.front().first.first+mov[dir][0];
		int nC = q.front().first.second+mov[dir][1];
		q.pop();
		if (nR < 0 || nR >= n || nC < 0 || nC >= m) continue;
		if (visited[dir][nR][nC]) continue;
		visited[dir][nR][nC] = true;
		answer[nR][nC] = 1;
		if (graph[nR][nC] == 1 && dir % 2 == 1)continue;
		else if (graph[nR][nC] == 2 && dir % 2 == 0)continue;
		else if (graph[nR][nC] == 9)continue;
		else if (graph[nR][nC] == 3) {
			if (dir < 2) {
				dir = (dir + 1) % 2;
			}
			else {
				dir = 2 + (dir + 1) % 2;
			}
		}
		else if (graph[nR][nC] == 4) {
			if (dir == 0) dir = 3;
			else if (dir == 3) dir = 0;
			else if (dir == 1) dir = 2;
			else dir = 1;
		}
		q.push({ {nR,nC},dir });
	}


}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >>graph[i][j];
			if (graph[i][j] == 9) {
				answer[i][j]=1;
				for (int k = 0; k < 4; k++) {
					visited[k][i][j] = true;
					q.push({ {i,j},k });
				}
			}
		}
	}
	bfs();
	int sum = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			sum+=answer[i][j];
		}
	}
	cout << sum;
}

코드(Kotlin)

import java.util.*
//상우하좌
val mov = arrayOf(arrayOf(-1,0),arrayOf(0,1),arrayOf(1,0),arrayOf(0,-1))
val q : Queue<Wind> = LinkedList<Wind>()
fun bfs(visited : Array<Array<BooleanArray>>,  n : Int, m : Int, graph : Array<CharArray>,answer : Array<IntArray>){

    while(q.isNotEmpty()){
        var (r,c,dir) = q.poll()
        val nR = r+mov[dir][0]
        val nC = c+mov[dir][1]
        if(nR<0 || nR>=n || nC<0 || nC>=m) continue
        if(visited[dir][nR][nC]) continue
        visited[dir][nR][nC]=true
        answer[nR][nC]=1
//        set.add(Pair(nR,nC))
        if(graph[nR][nC]=='1' && dir%2==1){
            continue
        }
        else if(graph[nR][nC]=='2'&& dir%2==0){
            continue
        }
        else if(graph[nR][nC]=='3'){
            if(dir>=2){
                dir = 2+(dir+1)%2
            }
            else{
                dir = (dir+1)%2
            }
        }
        else if(graph[nR][nC]=='4'){
            when{
                dir ==0 ->dir=3
                dir ==1 ->dir=2
                dir ==2 ->dir=1
                else -> dir=0
            }
        }
        else if(graph[nR][nC]=='9'){
            continue
        }//dir 변경 완료
        q.add(Wind(nR,nC,dir))
    }

}

fun main() = with(System.out.bufferedWriter()){
    val br= System.`in`.bufferedReader()
    var tk = StringTokenizer(br.readLine())
    val (n,m) = List(2){Integer.parseInt(tk.nextToken())}
    val graph = Array(n){CharArray(m)}
    val visited = Array(4){Array(n){BooleanArray(m)}}
//    val set = mutableSetOf<Pair<Int,Int>>()
    val answer = Array(n){IntArray(m)}

    for(i in 0 until n){
        tk = StringTokenizer(br.readLine())
        for(j in 0 until m){
            val num = tk.nextToken()
            graph[i][j]= num[0]
            if(graph[i][j] == '9'){
//                set.add(Pair(i,j))
                answer[i][j]=1
                for(dir in 0 until 4){
                    visited[dir][i][j]=true
                    q.add(Wind(i,j,dir))
                }
            }
        }
    }
    bfs(visited,n,m,graph,answer)
    var sum=0
    for(ans in answer){
        sum +=ans.sum()
    }
    write("${sum}")

    close()
}
data class Wind(var r : Int, var c : Int, var dir : Int)