언제나 처음처럼

[문제 링크]

BFS를 통해 같은 집합에 속한 정점들을 방문하면서 같은 레벨에 속한 정점들을 같은 숫자로 마킹한다.

이 과정에서 같은 레벨에 속했는데 이미 다른 숫자로 마킹이 되어있는 정점이 있는 경우 그 그래프는 이분그래프가 아니게 되므로 false를 반환한다.

모든 정점을 방문할 때 까지 위 과정을 반복하면서 false를 반환하지 않았다면 이분그래프이므로 true를 반환하도록 구현하면 원하는 결과를 얻을 수 있다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int V, E;
vector<int> adj[20001];
vector<int> visited;

bool bfs(int start) {
	queue<pair<int, int>> q;
	q.push({ start, 1 });
	visited[start] = 1;

	while (!q.empty()) {
		int here  = q.front().first;
		int color = q.front().second;
		q.pop();

		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i];
			
			if (visited[there] == 0) {
				visited[there] = -color;
				q.push({ there, -color });
			}
			else
				if (visited[there] != -color)
					return false;
		}
	}

	return true;
}

bool bfsAll() {
	visited = vector<int>(V + 1, 0);

	for (int i = 1; i <= V; i++)
		if (visited[i] == 0)
			if (!bfs(i)) return false;

	return true;
}

int main(void) {
	int tc;
	cin >> tc;

	while (tc--) {
		cin >> V >> E;
		for (int i = 1; i <= V; i++)
			adj[i].clear();

		for (int i = 0; i < E; i++) {
			int a, b;
			cin >> a >> b;
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
		
		if (bfsAll())
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 164 day

[문제 링크]

너비 우선 탐색을 공부하기 전에 한번 풀어봤던 문제였다. 그때는 몇시간을 고민해도 결국 시간초과의 늪에서 빠져나오지 못했었는데 너비 우선 탐색으로 접근하니까 어렵지 않게 풀 수 있었다.

입력받는 단계에서 R, B, O 의 위치를 미리 저장한 다음, R의 위치와 B의 위치를 queue에 담고 너비 우선 탐색을 시작한다.

기울였을 때 앞에 있는 볼보다 뒤에 있는 볼이 먼저 움직이는 상황을 방지하기 위해 기울이는 방향에 따라 더 앞에 있는 볼 먼저 움직이도록 구현하였다.

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;

struct Pos {
	int y;
	int x;

	bool operator== (const Pos& rhs)
	{
		if (y == rhs.y && x == rhs.x) 
			return true;
		else 
			return false;
	}
};

Pos R, B, O;
char board[10][10];
int N, M;
int dy[4] = { 0, 0, 1, -1 };
int dx[4] = { 1, -1, 0, 0 };

void Move_R(Pos& thereR, const Pos& thereB, int type)
{
	while (1) {
		Pos next = { thereR.y + dy[type], thereR.x + dx[type] };

		if (board[next.y][next.x] == '#') break;
		if (board[next.y][next.x] == 'O') {
			thereR = next;
			break;
		}
		else if (next == thereB) {
			break;
		}
		else {
			thereR = next;
		}
	}
}

void Move_B(const Pos& thereR, Pos& thereB, int type)
{
	while (1) {
		Pos next = { thereB.y + dy[type], thereB.x + dx[type] };

		if (board[next.y][next.x] == '#') break;
		if (board[next.y][next.x] == 'O') {
			thereB = next;
			break;
		}
		else if (next == thereR) {
			break;
		}
		else {
			thereB = next;
		}
	}
}

void MovingBall(Pos& thereR, Pos& thereB, int type)
{
	if (type == 0) { // 좌로 이동
		// 이동 방향 기준으로 R이 앞에 있는 경우
		if (thereR.y == thereB.y && thereR.x > thereB.x) {
			// R 먼저
			Move_R(thereR, thereB, type);
			Move_B(thereR, thereB, type);
		}
		else {
			// B 먼저
			Move_B(thereR, thereB, type);
			Move_R(thereR, thereB, type);
		}
	}

	else if (type == 1) { // 우로 이동
		// 이동 방향 기준으로 R이 앞에 있는 경우
		if (thereR.y == thereB.y && thereR.x < thereB.x) {
			// R 먼저
			Move_R(thereR, thereB, type);
			Move_B(thereR, thereB, type);
		}
		else {
			// B 먼저
			Move_B(thereR, thereB, type);
			Move_R(thereR, thereB, type);
		}
	}

	else if (type == 2) { // 아래로 이동
		// 이동 방향 기준으로 R이 앞에 있는 경우
		if (thereR.x == thereB.x && thereR.y > thereB.y) {
			// R 먼저
			Move_R(thereR, thereB, type);
			Move_B(thereR, thereB, type);
		}
		else {
			// B 먼저
			Move_B(thereR, thereB, type);
			Move_R(thereR, thereB, type);
		}
	}


	else if (type == 3) { // 위로 이동
		// 이동 방향 기준으로 R이 앞에 있는 경우
		if (thereR.x == thereB.x && thereR.y < thereB.y) {
			// R 먼저
			Move_R(thereR, thereB, type);
			Move_B(thereR, thereB, type);
		}
		else {
			// B 먼저
			Move_B(thereR, thereB, type);
			Move_R(thereR, thereB, type);
		}
	}
}

int bfs()
{
	queue<pair<pair<Pos, Pos>, int>> q;
	q.push({ { R, B }, 0 });

	while (!q.empty())
	{
		Pos hereR = q.front().first.first;
		Pos hereB = q.front().first.second;
		int move = q.front().second;

		q.pop();

		// 이동횟수 10회 초과 시 불가능
		if (move > 10) break;

		// R or B 가 구멍에 들어갔을 경우
		if (O == hereR || O == hereB)
		{
			if (O == hereB) // B가 구멍에 빠지면 실패 
				continue;
			else			// R만 구멍에 빠지면 성공
				return move;
		}

		for (int i = 0; i < 4; i++)
		{
			Pos thereR = hereR;
			Pos thereB = hereB;
			MovingBall(thereR, thereB, i);
			
			// 두 공다 움직이지 않았다면 건너뜀
			if (thereR == hereR && thereB == hereB) continue;

			q.push({ {thereR, thereB}, move + 1 });
		}
	}

	return -1;
}

int main(void)
{
	cin >> N >> M;

	for(int i=0; i<N; i++)
		for (int j = 0; j < M; j++)
		{
			cin >> board[i][j];

			if (board[i][j] == 'R')
				R = { i,j };
			else if (board[i][j] == 'B')
				B = { i,j };
			else if (board[i][j] == 'O')
				O = { i,j };
		}

	cout << bfs() << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 163 day