Boj 5213) Totem

문제

백준 5213

설명

인접리스트를 써서 구현하기도 한다는데, 타일 번호를 저장하는 tileNum[] 배열을 따로 둬서 타일번호가 같은지 체크하는 걸로 구현하였다. 그러면 남는건 간단한 BFS 문제가 된다.

이때 0-1 BFS, 즉 큐에서 꺼낸 후에 같은 타일이면 먼저 처리하면 될거라 생각해 삽질을 꽤 했다. 이러면 같은 타일의 두 점을 다른 지점에서 따로 접근하는 경우, 같은 타일에도 불구하고 다른거리로 처리가 되기 때문에 문제가 된다. 한 타일을 탐색하는 경우 타일의 두 지점을 한번에 큐에 넣어야지 이러한 문제가 생기지 않는다.

삽질하다 테스트 케이스를 모아놓은 깃헙 레포 를 찾았다.

시간 복잡도

O(\(N^2\))

코드

int n, w;
int board[1001 * 501], tileNum[1001 * 501], visits[1001 * 501];
int dx[]{ -1, 1, 0 , 0 };
int dy[]{0, 0, -1, 1 };

inline bool Valid(int x, int y)
{
	return x >= 0 && y >= 0 && x < w&& y < n&& board[y * w + x];
}

inline bool CanMove(int from, int to)
{
	return board[from] == board[to] || tileNum[from] == tileNum[to];
}

int main()
{
	fastio;
	cin >> n; w = 2*n;
	int cnt = 0;
	for (int i = 0; i < n; i++)
	{
		bool offset = i % 2;
		for (int j = offset; j < w - offset; j += 2)
		{
			cin >> board[i * w + j] >> board[i * w + j+1];
			tileNum[i * w + j] = tileNum[i * w + j + 1] = ++cnt;
		}
	}
	
	fill(visits, visits + 501 * 1001, -1);
	queue<int> q;
	q.push(0);

	int th = 0, destTile = -1, destPos;
	while (!q.empty())
	{
		int cur = q.front(); q.pop();
		if (destTile < tileNum[cur])
		{
			destTile = tileNum[cur];
			destPos = cur;
		}

		int cur_x = cur % w, cur_y = cur / w;
		for (int i = 0; i < 4; i++)
		{
			int x = cur_x + dx[i], y = cur_y + dy[i], d = y * w + x;
			if (!Valid(x, y) || !CanMove(cur, d)) continue;
			if (visits[d]>=0) continue;
			visits[d] = cur;
			q.push(d);
			// 같은 타일이 존재하면 한번에 처리
			if (tileNum[d + 1] == tileNum[d]) { visits[d+1] = cur; q.push(d + 1);}
			if (tileNum[d - 1] == tileNum[d]) { visits[d-1] = cur; q.push(d - 1);}
		}	
	}

	deque<int> ans; ans.push_front(destTile);
	while (destTile > 1)
	{
		destPos = visits[destPos];
		destTile = tileNum[destPos];
		if(ans.front() != destTile)
			ans.push_front(destTile);
	}

	cout << ans.size() << endl;
	for (auto a : ans) cout << a << ' ';
}