[BOJ] 2206 벽 부수고 이동하기(BFS, 3차원 배열)

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

범주: BFS, 3차원 배열을 이용한 DP

시간복잡도: O(N*M)

설명:

BFS를 진행하면서 2가지 상황에서 이동이 가능하다.

전제) 다음 노드는 한번도 접근되지 않은 노드이므로 최소 경로임이 보장된다. 

1) 다음 노드는 벽이 아니다(pos[r][c] == 0).

2) 다음 노드는 벽이지만(pos[r][c] == 1), 현재 노드는 벽을 부수지 않고 진행했다.

 

 

시도:

1) 백트래킹 -> 시간 초과

2) 2차원 배열 DP -> 4방향을 이용한 DP는 힘들다

 

 

가져갈 수 있는 팁:

1) 띄어쓰기로 표현되지 않은 입력은 scanf("%1d", __ )로 받아준다.

2) 3개 이상의 멤버들을 필요로 하는 경우, struct를 사용하는 것이 편하다.

(다른 방법: pair<pair<int, int> >)

3) 3차원 배열을 이용해서 장애물 index를 마련하여 최적화를 시도할 수 있다. 

 

#include<bits/stdc++.h>

using namespace std;

struct axis
{
	int row;
	int col;
	int wall;	
};

int N, M;
int pos[1001][1001];
int dist[1001][1001][2];
int orient[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

void bfs()
{
	queue<axis> q;
	q.push({0,0,0});
	dist[0][0][0] = 1;
	
	while(!q.empty())
	{
		int r = q.front().row;
		int c = q.front().col;
		int w = q.front().wall;
		q.pop();	
			
		if(r == N -1 && c == M - 1)
		{
			cout << dist[r][c][w];
			return;
		}
		
		for(int i = 0; i < 4; i++)
		{
			int nr = r + orient[i][0];
			int nc = c + orient[i][1];
			
			if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
			
			if(pos[nr][nc] == 0 && dist[nr][nc][w] == 0)
			{
				dist[nr][nc][w] = dist[r][c][w] + 1;
				q.push({nr, nc, w});
			}
			else if(pos[nr][nc] == 1 && w == 0 && dist[nr][nc][w+1] == 0)
			{
				dist[nr][nc][w+1] = dist[r][c][w] + 1;
				q.push({nr, nc, w+1});
			}
		}
	}
	
	cout << -1;
	return;
}

int main()
{
	
	cin >> N >> M;
	
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < M; j++)
		{
			scanf("%1d", &pos[i][j]);
		}
	}
		
	bfs();
	
	return 0;
}

 

주의할 점:

계속해서 문제를 틀렸었는데 그 이유는 ios::sync_with_stdio(NULL)를 쓰고 scanf와 cin을 같이 썼기 때문이다.

ios::sync_with_stdio(NULL)는 c++의 iostream과 c의 stdio를 동기화시켜주는데 이 경우, scanf와 cin을 같이 쓰면 문제가 생긴다. 

 

-해결책

1) ios::sync_with_stdio(NULL) 지우거나

2) cin >> N >> M 을 scanf("%d %d", &N, &M)으로 바꾸거나

3) scanf("%1d", &pos[i][j])말고, string으로 한번에 받은 뒤에 같은 열의 값들을 pos에 나누어준다.