백준 16933번 - 벽 부수고 이동하기3

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

16933번: 벽 부수고 이동하기 3

이번 문제도 벽 부수기 문제의 일종으로 벽을 주어진 횟수만큼 부순다. 단, 낮과 밤이 존재해서 낮에는 벽을 부술 수

있지만, 밤에는 벽을 부술 수 없다. 칸을 이동할때마다 낮과 밤이 순서대로 바뀌고, 만약 이동하지 않은경우에는

머물더라도 낮과 밤이 바뀌게 된다.

 

해당 문제를 푸는 알고리즘은 아래와 같다.

 

1. 미로의 map (행렬)을 만들어 탐색준비

 

2. 미로와 같은 행렬의 크기인 새로운 행렬 visit(방문확인 행렬) 을 생성한다. visit[x][y][z] 라고 했을 경우

x는 row 의 위치 y는 col 의 위치 z는 몇번째 벽을 부쉈는지의 index 로 mapping 시켜준다.

해당 3차 배열은 boolean 형으로 생성해준다.

 

3. Node class 를 생성하여 해당 노드에 행,열 위치정보와 현재 몇칸을 건너왔는지에 대한정보 그리고 몇개의 벽을 쉈는지에 대한 정보 그리고 현재 노드객체가 낮인지 밤인지에 대한 정보도 기입해준다.

 

4. 해당 Node 객체를 가지고 Queue 를 생성하여 Enqueue, Dequeue 를 반복하여 Queue 에 Node 객체가 사라질 때까지 너비탐색을 진행하여 미로를 탐색해준다.

 

5. Enqueue Dequeue 작업에서는 너비탐색으로 다음위치로 향할 경우에 해당 위치가 벽인지 아닌지 체크하고 방문배열도 체크해준다. 또한, 낮일경우와 밤이지만 벽을 부수지 않는 경우에는 기존 벽 부수기 문제와 같이 방문배열 체크와 Queue 에 Node 정보만 넣어주면 되지만, 밤인데 벽을 부숴야 할 경우에는  step 만 하나 늘려주고 방문배열은 건드리지 않고 새로운 Node 를 생성하여 Queue에 넣어준다.

 

6. Queue 에 모든 객체요소가 사라지거나 Queue 에 존재하는 Node 객체의 row,col 정보가 맨 마지막 row,col 인 경우에멈춰주고 답을 도출한다.

 

 

 

예시를 들기위해서 아래와 같은 미로가 존재한다고 해보자.

 

시작점은 day/night 가 존재하지 않고 처음 이동한 칸부터 day 를 적용해주면 된다.

 

 

(0,1)을 방문하였으므로 방문배열에는 아래와 같이 표시해주면 된다 표시가 안되어있는 칸은 모두 false 라고 생각하면 된다. 빨간점으로 표시된 부분은 true 값이라고 생각하면 된다.

 

또한 오른쪽칸으로 한칸 이동 하면 map 과 방문배열은 아래와 같이 나타낼 수 있다.

이제, 오른쪽으로 이동하는 경우가 문제인데 현재 Node 가 벽을 부술수 있음에도 시각정보가 밤이므로 벽 자체를 

부술 기회가 주어지지 않는다. 이럴경우에는 step 하나를 추가하고, 시각을 바꾼다음 해당 Node를 Queue 에 push 해준다. 

Crash = 1 인 방문배열은 건들지 않는다. => 아직 방문한것이 아니기 때문

 

 

해당 위치의 Node 가 낮일경우 다시 방문해주면 위의 그림과 같다.

해당 시각에서는 낮 시간이므로 벽을 부술수 있고 부순뒤에 map과 방문배열은 아래와 같다.

위와 같은 로직으로 코드를 구현하면 아래와 같다.

 

1. JAVA 

import java.io.*;
import java.util.*;

public class Main {
	
	static int N,M,C;
	static int[] dr = {0,0,1,-1};
	static int[] dc = {1,-1,0,0};
	static int[][] map;
	static boolean[][][] visit;
	
	static class Node {
		int r,c,step,crash,day;
		
		public Node(int r,int c, int step, int crash, int day) {
			this.r = r;
			this.c = c;
			this.step = step;
			this.crash = crash;
			this.day = day;
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] nmc = br.readLine().split(" ");
		N = Integer.parseInt(nmc[0]);
		M = Integer.parseInt(nmc[1]);
		C = Integer.parseInt(nmc[2]);
		
		map = new int[N][M];
		visit = new boolean[N][M][11];
		
		for (int i = 0; i < N; i++) {
			String[] rc = br.readLine().split("");
			for (int j = 0; j <M; j++) {
				map[i][j] = Integer.parseInt(rc[j]);
			}
		}
		
		int result = bfs();
		
		bw.write(result + "");
		bw.close();
		br.close();
		
		
	}
	
	static int bfs() {
		Queue<Node> queue = new ArrayDeque<>(); 
		queue.offer(new Node(0,0,1,0,1));
		visit[0][0][0] = true;
		
		while(!queue.isEmpty()) {
			Node nd = queue.poll();
			
			if (nd.r == N-1 && nd.c == M- 1) return nd.step;
			
			for (int i = 0; i < 4; i++) {
				int nr = nd.r + dr[i];
				int nc = nd.c + dc[i];
				
				if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
				
				if (map[nr][nc] == 0 && !visit[nr][nc][nd.crash]) {
					queue.offer(new Node(nr,nc,nd.step+1,nd.crash,-1*nd.day));
					visit[nr][nc][nd.crash] = true;
				}
				
				if (map[nr][nc] == 1 && nd.crash < C &&!visit[nr][nc][nd.crash+1]) {
					if (nd.day == 1) {
						queue.offer(new Node(nr,nc,nd.step+1,nd.crash+1,-1*nd.day));
						visit[nr][nc][nd.crash+1] = true;
					} else {
						queue.offer(new Node(nd.r,nd.c,nd.step+1,nd.crash,-1*nd.day));
					}
				}
			}
		}//while
		
		return -1;
	}
}

 

 

2. C++

#include <iostream>
#include <queue>

using namespace std;

int N,M,C;
int map[1001][1001];
bool visit[1001][1001][11];
int dr[4] = {1,-1,0,0};
int dc[4] = {0,0,1,-1};

typedef struct {
    int r,c,step,crash,day_yn;
} nods;

int bfs();

int main()
{
    scanf("%d %d %d",&N,&M,&C);
    
    char line[M+1];
    
    for (int i = 0; i < N; i++) {
        scanf("%s",line);
        for (int j= 0 ;j < M; j++) {
            map[i][j] = line[j] - '0';
        }
    }
    
    printf("%d",bfs());
    
    return 0;
}

int bfs() {
    queue<nods> q;
    nods nod = {0,0,1,0,1};
    q.push(nod);
    visit[0][0][0] = true;
    
    while(!q.empty()) {
        nods nd = q.front();
        q.pop();
        
        if (nd.r == N-1 && nd.c == M-1) return nd.step;
        
        for (int i = 0; i < 4; i++) {
            int nr = nd.r + dr[i];
            int nc = nd.c + dc[i];
            
            if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
            
            if (map[nr][nc] == 0 && !visit[nr][nc][nd.crash]) {
                nods ns = {nr,nc,nd.step+1,nd.crash, -1 *nd.day_yn};
                q.push(ns);
                visit[nr][nc][nd.crash] = true;
            }
            
            if (map[nr][nc] == 1 && nd.crash < C &&!visit[nr][nc][nd.crash+1]) {
                nods ns;
                if (nd.day_yn == 1) {
                    ns = {nr,nc,nd.step+1,nd.crash+1, -1 *nd.day_yn};
                    visit[nr][nc][nd.crash+1] = true;   
                } else {
                    ns = {nd.r,nd.c,nd.step+1,nd.crash, -1 *nd.day_yn};
                }
                q.push(ns);
            }
        }
    }
    return -1;
}