BOJ 2206번: 벽 부수고 이동하기

문제

문제 바로가기> BOJ 2206번: 벽 부수고 이동하기

2206번: 벽 부수고 이동하기

 

풀이

벽을 하나씩 제거 + BFS 하는 경우, O(N^2*M^2)으로 시간 초과가 발생한다.

 

생각해보면, 어느 지점(y, x)에 도착할 때,

남은 기회가 있거나 or 없거나 둘 중 하나의 상태로 도착할 것이다.

이 점을 이용해서 BFS 탐색을 진행하면, BFS를 한번만 돌려도 문제를 풀수 있다!

 

추가로, 가중치가 동일할 때 최단 경로를 찾는 문제이므로,

가장 먼저 (N-1, M-1)에 도착했을 때의 dist를 반환해주면 된다!

 

C++

#include<iostream>
#include<vector>
#include<queue>
#define INF 100000001
#define MAX 1001
#define WALL 1
#define EMPTY 0
using namespace std;

struct DATA { int y, x, chance; };

int N, M;
int map[MAX][MAX];
int dist[MAX][MAX][2];
int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };

void input() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		string str; cin >> str;
		for (int j = 0; j < M; j++) map[i][j] = str[j] - '0';
	}
}

int solution() {
	queue<DATA> q;
	q.push({ 0,0,1 }); // (0,0)에서 출발, 벽을 꺨 수 있는 기회 한번
	dist[0][0][1] = 1;

	while (!q.empty()) {
		int y = q.front().y;
		int x = q.front().x;
		int chance = q.front().chance;
		q.pop();

		if(y==N-1 && x==M-1) return dist[y][x][chance]; // 도착한 경우
		for(int d=0; d<4; d++){
			int ny = y+dy[d];
			int nx = x+dx[d];
			if(ny<0 || ny>=N || nx<0 || nx>=M || dist[ny][nx][chance]) continue; // 범위를 벗어나는 경우, 이미 방문한 경우
			if(map[ny][nx]==WALL && chance){ // 벽인데, 남은 기회가 있는 경우
				dist[ny][nx][0] = dist[y][x][1]+1;
				q.push({ny, nx, 0});
			}
			else if(map[ny][nx]==EMPTY){ // 벽이 아닌 경우
				dist[ny][nx][chance] = dist[y][x][chance]+1;
				q.push({ny, nx, chance});
			}
		}
	}
	return -1; // 도착 불가능한 경우
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	input();
	cout << solution();
}

 

JAVA

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

public class Main {
	
	static final int[] dy = {-1, 1, 0, 0};
	static final int[] dx = {0, 0, -1, 1};

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int[][][] dist = new int[N][M][2];
		boolean[][] map = new boolean[N][M];
		
		for(int i=0; i<N; i++) {
			String line = br.readLine();
			for(int j=0; j<M; j++) map[i][j] = (line.charAt(j)=='0'?false:true);
		}
		
		ArrayDeque<int[]> q = new ArrayDeque<>();
		q.offer(new int[]{0, 0, 1});
		dist[0][0][1] = 1;
		
		while(!q.isEmpty()) {
			int y = q.peek()[0];
			int x = q.peek()[1];
			int c = q.peek()[2];
			q.poll();
			
			if(y==N-1 && x==M-1) {
				System.out.println(dist[y][x][c]);
				return;
			}
			
			for(int d=0; d<4; d++) {
				int ny = y+dy[d];
				int nx = x+dx[d];
				if(ny<0 || ny>=N || nx<0 || nx>=M || dist[ny][nx][c]>0) continue;
				if(map[ny][nx] && c==1) { // wall
					dist[ny][nx][0] = dist[y][x][1]+1;
					q.offer(new int[] {ny, nx, 0});
				}
				else if(!map[ny][nx]) { // empty
					dist[ny][nx][c] = dist[y][x][c]+1;
					q.offer(new int[] {ny, nx, c});
				}
			}
		}
		System.out.println(-1);
		br.close();
	}
}