[Baekjoon] 11967번: 불켜기

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

11967번: 불켜기

 

그래프 탐색 알고리즘과 관련한 문제는 자신 있다고 생각했는데, 문제에서 요구하는 것 잘못 파악 + 문제에 들어있는 함정 때문에 처음 작성했던 코드가 왜 틀렸는지 이해하느라 엄청난 시간을 소모해버렸당

 

---

 

문제 해결 과정

착안

시작 지점으로부터 방을 방문할 때마다, 방에 존재하는 모든 스위치를 켜면서 불이 켜진 방의 갯수를 증가시킨다. 이후 인접한 방 중에서 불이 켜져 있는 방들을 너비 우선 탐색(breadth-first search) 알고리즘에 기반하여 방문한다. 이때, 스위치를 켜서 새로 불이 켜진 방이 향후 이동할 경로가 아닌, 이미 방문했던 지점과 연결되는 경우에 주의한다.

 

구현

기본적인 너비 우선 탐색 알고리즘에 기반해 코드를 작성하면, 처음에는 시작 지점과 인접한 방이지만 불이 켜져 있지 않아 방문하지 않고 지나갔던 방이 나중에 불이 켜져 방문해야하는 경우를 해결할 수 없다. 따라서, 이와 같은 부분을 해결하기 위해 이미 방문한 지점에 대해서도 필요한 경우(옆 방의 불이 새로 켜진 경우)에는 다시 방문하도록 코드 상에서 처리하는 것이 필요하다. 이러한 부분 때문에 이 문제를 해결할 때 주의할 점이 몇 가지 있다.

 

우선 큐(queue) 자료 구조를 활용해 너비 우선 탐색 알고리즘을 구현할 때, 큐가 빌 때까지 반복하는 구문에서 이미 방문했던 방일 경우 점프 구문 등을 사용해 건너뛸 수 없다(필요한 경우에는 다시 방문해야하므로). 따라서, 큐에 앞으로 방문하려는 방을 추가할 때 해당 방의 방문 여부도 미리 표시해주어야한다(불필요하게 중복 방문하지 않도록 방문 여부를 표시).

 

한편, 불이 새로 켜지는 방이 있을 때 불이 이미 켜져있는 경로로 이동해 그 방을 방문할 수 있으면 해당 방을 지나는 새로운 경로도 추가로 탐색해야 한다. 따라서 불이 새로 켜진 방이 방문 가능한 경로 상에 있는지 판단한 다음, 위에서와 같이 불이 켜진 방을 큐에 넣으면서 방문 여부를 미리 표시하면 추가적으로 새로운 경로의 탐색이 가능하다.

* 참고1) 불이 새로 켜진 방의 인접한 방 중에 이미 방문한 방이 하나라도 있으면, 그 경로를 따라 방문 가능하다.

* 참고2) 불이 새로 켜진 방 대신, 그 방과 인접한 이미 방문했던 방을 재방문하도록 큐에 넣어도 된다.

 

요약하자면, 이 문제를 해결하기 위해서는

1) 불필요한 중복 방문은 방지하면서도 필요한 경우에는 방문했던 지점을 재방문할 수 있어야하며,

2) 불이 새로 켜지는 방을 방문할 수 있는지 판단하여 방문할 수 있으면 새로운 탐색 경로를 추가해야 한다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <map>
#include <vector>
#include <queue>

using namespace std;

#define Coord pair<int, int>
#define X first
#define Y second

int Map[102][102];		// 0: Switch Off, 1: Switch On, 2: Connected to (1, 1)
map<Coord, vector<Coord>> Switches;

int dx[4] = { -1, 1,  0, 0 };
int dy[4] = { 0, 0, -1, 1 };

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N, M;
	cin >> N >> M;
	while (M--)
	{
		int x, y, a, b;
		cin >> x >> y >> a >> b;
		Switches[Coord{ x, y }].push_back(Coord{ a, b });
	}

	queue<Coord> q;
	q.push(Coord{ 1, 1 });
	Map[1][1] = 2;
	int lights = 1;
	while (!q.empty())
	{
		Coord curr = q.front();
		q.pop();

		for (Coord c : Switches[curr])
			if (!Map[c.X][c.Y])
			{
				Map[c.X][c.Y] = 1;
				lights++;
				// whenever switch turns on,
				// find adjacent room connected with (1, 1)
				for (int i = 0; i < 4; i++)
				{
					int x = c.X + dx[i];
					int y = c.Y + dy[i];
					// if exists, then add new room to queue
					if (Map[x][y] == 2)
					{
						Map[c.X][c.Y] = 2;
						q.push(c);
						break;
					}
				}
			}

		for (int i = 0; i < 4; i++)
		{
			int x = curr.X + dx[i];
			int y = curr.Y + dy[i];
			if (Map[x][y] == 1)
			{
				Map[x][y] = 2;
				q.push(Coord{ x, y });
			}
		}
	}

	cout << lights << "\n";
	return 0;
}

 

실행 결과