백준 2206번 : 벽 부수고 이동하기

문제 접근

---

연구소 문제처럼 브루트 포스를 통해 BFS 로 풀면 시간복잡도가 O(N^2*M^2) 이 나오고, 범위로 계산해봤을 때 1,000,000,000,000 이 나와서 이렇게 풀면 안 된다. 고민해보다가 경로 별로 isbroken 이라는 변수를 주어서 딱 한 번 막혔을 때 부수고 true 로 바뀌도록 구현해봤다.

 

처음에 메모리 초과가 계속 나서 q 에 넣어줄 때 visited 를 true 로 설정하니 중복이 없어져 해결되었고, 이후에는 틀렸습니다가 계속 나왔다. 확인해보니 시작 부분이 1이어도 벽을 부수지 않았다고 넣어주는 경우가 있어 고쳤다. 하지만 조건 보니 시작이랑 끝은 항상 0이어서 소용이 없다..

 

저번에 종만북에서 읽었던 스캐폴딩이 생각나서 파일 입출력으로 N=M=1000 일 때를 확인해봤는데 1999로 잘 나온다. 질문 검색에 있는 테스트 케이스들도 혹시 몰라서 다 넣어봤는데 잘 된다. 뭐가 문제지?

 

알고보니 각 줄은 최대 1000자까지 입력되는데 int 형 변수로는 이를 초과해서 다른 값이 들어가게 되어 틀린 것이었다.  일단 빠르게 되나 해보려고 scanf("%1d",&input[j-1]); 로 확인했고, 이후 C 입출력이랑 같이 안 쓰려고 cin.get() 으로 처리했다. cin.ignore() 로 버퍼 비우는 방식으로 해보고 싶었는데 잘 안 돼서 그냥 '\n' 인 경우 --j 하는 방식으로 해결했다.

 

주의할 점!

1. 입력 데이터형의 크기를 꼭 확인하자! ㅠㅡㅠ

2. 중복을 최소화해서 메모리 낭비를 방지하자!

 

 

문제 코드

---

#include <iostream>
#include <queue>
#include <tuple>
#include <algorithm>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	
	// 먼저 (x,y) 에 도달한 건 isbroken 상태가 같다면 나중에 도달한 것보다 무조건 빨리 진행된다.
	int map[1002][1002];
	bool visited[1002][1002][2] = {false,};
	int dx[4] = {0,1,0,-1};
	int dy[4] = {1,0,-1,0};
	
    // 각각 x 좌표, y 좌표, 벽을 부순적이 있는지 여부에 해당한다.
	queue<tuple<int, int, bool>> q;
	
    // rep 은 BFS 한 번 확인할 때 큐에 들어가 있는 좌표의 수이다.
    // next_rep 은 이번 rep 에서 큐에 넣은 좌표의 수이다. (1,1) 넣으면 rep 이 1 이므로 미리 초기화했다.
    // isFind 는 (N,M) 에 도착했는지 여부를 확인하는 bool 변수이다.
	int N, M, x, y, next_rep, ans = 0, rep = 1;
	bool isbroken, isFind = false;
	char input;
	
	fill(&map[0][0], &map[1001][1001], 2);
	
	cin>>N>>M;
	
    // 숫자를 붙여서 입력하기에 0,1 중 하나이니 10으로 나눈 나머지로 입력했다.
	// 입력은 1000자리까지..! int 형에 못 담는다..! 조심해!
	for(int i=1; i<=N; ++i)
	{
		for(int j=1; j<=M; ++j)
		{
			input = cin.get();
			
			if(input!='\n')
				map[i][j] = input-'0';
			
			else
				--j;
		}
	}
	
    // map 에 잘 들어갔는지 확인하는 부분.
	/*
	for(int i=0; i<N+2; ++i)
	{
		for(int j=0; j<M+2; ++j)
		{
			cout<<map[i][j];
		}
		cout<<'\n';
	}
	*/
	
    // (1,1) 에서 시작하고, 시작하는 부분에 벽이 있으면 깨고 시작해야하므로 조건을 붙여놨다.
	q.push(make_tuple(1,1,map[1][1]==1));
	
	while(!q.empty() && !isFind)
	{
		next_rep=0;
		
		while(rep--)
		{
        	// tie 를 통해 미리 만들어놓은 x, y, isbroken 에 한 번에 값을 넣어줬다.
			tie(x, y, isbroken) = q.front();
			q.pop();
            
            // BFS 진행 과정 확인하기 위해 작성한 부분.
			//cout<<"Trial "<<ans<<" : ("<<x<<", "<<y<<") - "<<(isbroken)?"True":"False";
			//cout<<'\n';
			
			if(x==N && y==M)
			{
				isFind = true;
				break;
			}
			
            // 상하좌우 방문했는지 여부 확인해보고, 해당 부분이 0이라면 push.
            // isbroken 이 false 고, 해당 부분이 1이라면 isbroken 을 true 로 두고 push.
            // visited 를 먼저한 이유는 중복해서 큐에 들어가는 것을 방지하기 위함이다.
			for(int i=0; i<4; ++i)
			{
				if(!visited[x+dx[i]][y+dy[i]][isbroken])
				{
					if(map[x+dx[i]][y+dy[i]] == 0)
					{
						q.push(make_tuple(x+dx[i],y+dy[i],isbroken));
						visited[x+dx[i]][y+dy[i]][isbroken] = true;
						++next_rep;
					}
					else if(!isbroken && !visited[x+dx[i]][y+dy[i]][1] && map[x+dx[i]][y+dy[i]]==1)
					{
						q.push(make_tuple(x+dx[i],y+dy[i],true));
						visited[x+dx[i]][y+dy[i]][1] = true;
						++next_rep;
					}
				}
			}
		}
		
		rep = next_rep;
		++ans;
	}
	
	if(!isFind)
		cout<<"-1\n";
	else
		cout<<ans<<'\n';
}

 

결과 - 장렬한 전투의 흔적

---

중복과 입력 데이터 크기만 신경 썼더라면...