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

🔒[문제 url]

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

🔑알고리즘

탐색 + 최단 경로? BFS!!

탐색을 진행하기 전까진 벽을 부수고 가는 길이 빠를지, 부수지 않는 것이 빠를지 알 수 없는 상황. 그렇다면?

• 벽을 부순 경로, 부수지 않고 간 경로를 나누어 방문 경로를 두 가지로 확인!

int visited[2][1000][1000]; // [0][][] : 벽 부숨, [1][][] : 벽 안 부숨

• 경우의 수는?
  1. 벽을 부순 상태에서 벽을 만난 경우
  - 더이상 갈 수 없으므로 continue
  2. 벽을 부수지 않은 상태에서 벽을 만난 경우
  - 방문 경로를 전환하여 계속 탐색한다.
  3. 벽을 부순 상태에서 길을 만난 경우
  4. 벽을 부수지 않은 상태에서 길을 만난경우
  - 3, 4번은 모두 방문 경로를 유지한 채 계속 탐색한다.
  
  
• queue에 정점을 push할 때, 방문 경로의 전환 여부를 알기위해 벽을 부수었는지의 여부또한 좌표와 함께 담는다.

struct NODE
{
	int x;
	int y;
	int bomb; // 0 : 벽 부숨, 1 : 벽 안 부숨
};
queue<NODE> q;
q.push({ x, y, 1 });

이후 (N,M) 좌표에 도달하면 경로의 길이 반환, 도달하지 못하면 -1을 반환한다.

🐾부분 코드

void INPUT()
{
	//ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			scanf("%1d", &map[i][j]);
}

<입력 함수>
숫자를 하나씩 받고싶은 경우 다음의 c언어 코드를 이용한다.

scanf("%1d", &map[i][j]);

이때 C와 C++의 동기화 차단 코드를 지워주는 것을 잊지말자.

//ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int BFS(int x, int y)
{
	struct NODE
	{
		int x;
		int y;
		int bomb; // 0 : 벽 부숨, 1 : 벽 안 부숨
	};
	queue<NODE> q;
	q.push({ x, y, 1 });

	visited[1][x][y] = 1;

	while (!q.empty())
	{

		NODE now = q.front();
		q.pop();

		if (now.x == n - 1 && now.y == m - 1)
			return visited[now.bomb][now.x][now.y];

		for (int i = 0; i < 4; i++)
		{
			int dp[4][2] = { {0,1},{0,-1},{1,0},{-1,0} }; // 우 좌 하 상
			int nx = now.x + dp[i][0], ny = now.y + dp[i][1];

			if (0 <= nx && nx < n && 0 <= ny && ny < m)
			{
				/*
				1. 벽 부순 상태에서 벽 만났을 때 : continue
				2. 벽 안 부순 상태에서 벽 만났을 때 : visited 전환, q push


				3. 벽 안 부순 상태에서 길 만났을 때
				4. 벽 부순 상태에서 길 만났을 때

				3, 4번 모두 visited 전환없이 q에 push
				*/

				if (!visited[0][nx][ny] && now.bomb == 1 && map[nx][ny] == 1)
				{// 2번 케이스
					q.push({ nx,ny,0 });
					visited[0][nx][ny] = visited[1][now.x][now.y] + 1;
				}
				else if (!visited[now.bomb][nx][ny] && map[nx][ny] == 0)
				{// 3,4번 케이스
					q.push({ nx,ny,now.bomb });
					visited[now.bomb][nx][ny] = visited[now.bomb][now.x][now.y] + 1;
				}

			}
		}// for end

	}
	return -1;
}

<BFS 함수>
위에서 언급한 알고리즘에 따라, visited 배열(방문 경로의 길이)를 갱신해준다.
1번 케이스는 고려하지 않는다.
2번 케이스는 정점의 bomb 정보를 통해, 벽을 만난 경우 방문 경로를 전환(안 부순 경로에서 부순 경로로)한 후 계속 탐색한다.
3, 4번 케이스는 길을 만난 경우에 bomb 여부에 상관없이 탐색을 진행한다.

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stdio.h>
#include <ctime>
#include <memory.h> // memset
#include <numeric>
#include <sstream>
using namespace std;

int n, m;
int map[1000][1000];
int visited[2][1000][1000]; // [0][][] : 벽 부숨, [1][][] : 벽 안 부숨

void INPUT()
{
	//ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			scanf("%1d", &map[i][j]);
}

int BFS(int x, int y)
{
	struct NODE
	{
		int x;
		int y;
		int bomb; // 0 : 벽 부숨, 1 : 벽 안 부숨
	};
	queue<NODE> q;
	q.push({ x, y, 1 });

	visited[1][x][y] = 1;

	while (!q.empty())
	{

		NODE now = q.front();
		q.pop();

		if (now.x == n - 1 && now.y == m - 1)
			return visited[now.bomb][now.x][now.y];

		for (int i = 0; i < 4; i++)
		{
			int dp[4][2] = { {0,1},{0,-1},{1,0},{-1,0} }; // 우 좌 하 상
			int nx = now.x + dp[i][0], ny = now.y + dp[i][1];

			if (0 <= nx && nx < n && 0 <= ny && ny < m)
			{
				/*
				1. 벽 안 부순 상태에서 벽 만났을 때 : visited 전환, q push
				2. 벽 부순 상태에서 벽 만났을 때 : continue


				3. 벽 안 부순 상태에서 길 만났을 때
				4. 벽 부순 상태에서 길 만났을 때

				3, 4번 모두 visited 전환없이 q에 push
				*/

				if (!visited[0][nx][ny] && now.bomb == 1 && map[nx][ny] == 1)
				{
					q.push({ nx,ny,0 });
					visited[0][nx][ny] = visited[1][now.x][now.y] + 1;
				}
				else if (!visited[now.bomb][nx][ny] && map[nx][ny] == 0)
				{
					q.push({ nx,ny,now.bomb });
					visited[now.bomb][nx][ny] = visited[now.bomb][now.x][now.y] + 1;
				}

			}
		}

	}
	return -1;
}

void SOLVE()
{
	cout << BFS(0, 0);
}

int main()
{
	INPUT();

	SOLVE();
}

🥇문제 후기

문제를 처음 만난 날 풀이 실패한 문제.. 알고리즘을 생각해내지 못해 구글링한 후 며칠 뒤에 다시 풀어서 맞았다. 심지어, 방문 경로를 처리하는 데에 시간도 꽤 걸렸다ㅠㅠ..
경로를 나누어서 생각하면 된다는 간단한 아이디어를 왜 생각해내지 못했을까 아쉽긴하지만, 이번 데이터를 기반으로 앞으론 같은 상황에서 빠르게 문제를 해결할 수 있기를!