언제나 처음처럼

[문제 링크]

https://onlytrying.tistory.com/229    

예전에 풀었던 토마토 문제와 동일한 문제였다.

차이점은 상자의 상태가 3차원 배열이라는 점이다.

따라서, 기존의 구현 코드에서 상자를 3차원 배열로 변경하고 Z 좌표가 바뀌는 경우를 추가해주었다.

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

struct boxPos {
	int z, y, x;
};

int M, N, H;
int box[101][101][101];
queue<boxPos> ripeTomatoPosQ;
int dz[6] = { 0,0,0,0,1,-1 };
int dy[6] = { 0,0,1,-1,0,0 };
int dx[6] = { 1,-1,0,0,0,0 };

int getDay(int unripeTomato) {
	int day = 0;

	while (unripeTomato > 0) {
		day++;

		int newRipeTomatoCnt = ripeTomatoPosQ.size();
		// 안익은 토마토가 남아있는 상태에서 새롭게 익은 토마토가 없다면 토마토를 모두 익히는건 불가능하다.
		if (newRipeTomatoCnt == 0)
			return -1;

		for (int i = 0; i < newRipeTomatoCnt; i++) {
			int hereZ = ripeTomatoPosQ.front().z;
			int hereY = ripeTomatoPosQ.front().y;
			int hereX = ripeTomatoPosQ.front().x;
			ripeTomatoPosQ.pop();

			// 주변의 토마토를 익힌다.
			for (int i = 0; i < 6; i++) {
				int nearZ = hereZ + dz[i];
				int nearY = hereY + dy[i];
				int nearX = hereX + dx[i];

				if (nearZ >= 0 && nearZ < H && nearY >= 0 && nearY < N && nearX >= 0 && nearX < M)
					if (box[nearZ][nearY][nearX] == 0) {
						// 안익은 토마토를 익은 토마토로 바꾸고 안익은 토마토의 갯수를 1 감소시킨다.
						box[nearZ][nearY][nearX] = 1;
						unripeTomato--;

						// 새롭게 익은 토마토의 좌표를 큐에 담는다.
						ripeTomatoPosQ.push({ nearZ, nearY, nearX });
					}
			}
		}
	}

	return day;
}

int main(void) {
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	cin >> M >> N >> H;

	int unripeTomato = 0;
	for (int z = 0; z < H; z++) {
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < M; x++) {
				int state;
				cin >> state;
				box[z][y][x] = state;
				if (state == 0)
					unripeTomato++;
				else if (state == 1)
					ripeTomatoPosQ.push({ z,y,x });
			}
		}
	}

	cout << getDay(unripeTomato) << endl;

	return 0;
}

[문제 링크]

전체 그래프를 탐색하면서 아직 방문하지 않은 섬을 만나면 해당 섬의 좌표를 시작으로 하는 bfs를 수행하여 하나로 연결된 섬을 찾는다.

모든 좌표를 탐색했을 때 수행한 bfs 횟수가 곧 섬의 개수가 된다.

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

int w, h;
bool adj[50][50];
bool visited[50][50];
int dy[8] = { 0,0,-1,-1,-1,1,1,1 };
int dx[8] = { 1,-1,0,1,-1,0,1,-1 };

struct Pos {
	int y;
	int x;
};

void bfs(int startY, int startX) {
	queue<Pos> q;
	q.push({ startY, startX });
	visited[startY][startX] = true;

	while (!q.empty()) {
		int hereY = q.front().y;
		int hereX = q.front().x;
		q.pop();

		for (int i = 0; i < 8; i++) {
			int nextY = hereY + dy[i];
			int nextX = hereX + dx[i];

			if(nextY >= 0 && nextY < h && nextX >= 0 && nextX < w)
				if (adj[nextY][nextX] && !visited[nextY][nextX]) {
					q.push({ nextY, nextX });
					visited[nextY][nextX] = true;
				}
		}
	}
}

int getIslandCount() {
	int cnt = 0;

	for(int y=0; y<h; y++)
		for (int x = 0; x < w; x++) {
			if (adj[y][x] && !visited[y][x]) {
				cnt++;
				bfs(y, x);
			}
		}

	return cnt;
}

int main(void) {
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	while (true) {
		cin >> w >> h;
		if (w == 0 && h == 0)
			break;
		memset(adj, false, sizeof(adj));
		memset(visited, false, sizeof(visited));

		for (int y = 0; y < h; y++) {
			for (int x = 0; x < w; x++) {
				int n;
				cin >> n;
				adj[y][x] = n;
			}
		}
				
		cout << getIslandCount() << '\n';
	}

	return 0;
}

[문제 링크]

문제를 풀기 전에 연결 요소가 뭔지 알아야 할 필요가 있다.

연결 요소란? 그래프에서 하나로 연결된 정점들의 집합이라고 생각하면 된다.

그래프의 모든 정점을 방문할 때 까지 bfs나 dfs를 수행한 다음, 수행한 횟수가 곧 연결 요소의 갯수가 된다.

정점의 개수가 많고 양방향 그래프로 표현해야 하기 때문에 인접 행렬보단 인접 리스트로 그래프를 구현하는 것이 효율적이고 직관적이라고 생각한다.

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

int N, M;
vector<int> adj[1001];
bool visited[1001];

void bfs(int start) {
	queue<int> q;
	q.push(start);
	visited[start] = true;

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

		for (int i = 0; i < adj[here].size(); i++) {
			int next = adj[here][i];
			
			if (!visited[next]) {
				q.push(next);
				visited[next] = true;
			}
		}
	}
}

int getConnectedComponent() {
	int result = 0;

	for (int i = 1; i <= N; i++) {
		if (!visited[i]) {
			result++;
			bfs(i);
		}
	}

	return result;
}

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

	// 양방향 그래프로 구현할 것
	while(M--) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	cout << getConnectedComponent() << endl;

	return 0;
}

[문제 링크]

수빈이가  위치한 좌표를 시작으로 +1 하는 경우, -1 하는 경우, *2 하는 경우 도달하는 좌표를 큐에 담는 방식으로 bfs를 수행하면 정답을 얻을 수 있다.

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

bool visited[100001];
int N, K;

int bfs() {
	queue<pair<int, int>> q;
	q.push({N, 0});
	visited[N] = true;

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

		if (here == K) return sec;

		sec++;
		int next = here + 1;
		if (next <= 100000 && !visited[next]) {
			q.push({ next, sec });
			visited[next] = true;
		}
		
		next = here - 1;
		if (next >= 0 && !visited[next]) {
			q.push({ next, sec });
			visited[next] = true;
		}

		next = here * 2;
		if (next <= 100000 && !visited[next]) {
			q.push({ next, sec });
			visited[next] = true;
		}
	}

	// 이 행에 도달했다면 만나는건 불가능(가능성 0%)
	return -1;
}

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

	cout << bfs() << endl;
	
	return 0;
}

[문제 링크]

간단한 그래프 탐색 문제였다.

그래프를 탐색하면서 배추가 있는 땅을 시작으로 하는 bfs를 수행하고 인접해 있는 배추를 방문 표시한다.

모든 좌표를 탐색했을 때 bfs 호출 횟수가 지렁이의 마리 수가 된다.

#include <iostream>
#include <cstring>
#include <queue>
#include <stack>
using namespace std;

// M: 가로길이(x), N: 세로길이(y), K: 배추가 심어진 개수
int M, N, K;
bool adj[50][50];
bool visited[50][50];
int dy[4] = { 0,0,-1,1 };
int dx[4] = { 1,-1,0,0 };

struct Pos {
	int y;
	int x;
};

void bfs(int startY, int startX) {
	queue<Pos> q;
	q.push({ startY, startX });
	visited[startY][startX] = true;

	while (!q.empty()) {
		int hereY = q.front().y;
		int hereX = q.front().x;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nextY = hereY + dy[i];
			int nextX = hereX + dx[i];

			if (nextY >= 0 && nextY < N && nextX >= 0 && nextX < M) {
				if (adj[nextY][nextX] && !visited[nextY][nextX]) {
					q.push({ nextY, nextX });
					visited[nextY][nextX] = true;
				}
			}
		}
	}
}

void dfsStack(int startY, int startX) {
	stack<Pos> stk;
	stk.push({ startY, startX });
	visited[startY][startX] = true;

	while (!stk.empty()) {
		int hereY = stk.top().y;
		int hereX = stk.top().x;
		stk.pop();

		for (int i = 0; i < 4; i++) {
			int nextY = hereY + dy[i];
			int nextX = hereX + dx[i];

			if (nextY >= 0 && nextY < N && nextX >= 0 && nextX < M)
				if (adj[nextY][nextX] && !visited[nextY][nextX]) {
					stk.push({ nextY, nextX });
					visited[nextY][nextX] = true;
				}
		}
	}
}

void dfsRecursion(int startY, int startX) {
	visited[startY][startX] = true;

	for (int i = 0; i < 4; i++) {
		int nextY = startY + dy[i];
		int nextX = startX + dx[i];

		if (nextY >= 0 && nextY < N && nextX >= 0 && nextX < M)
			if (adj[nextY][nextX] && !visited[nextY][nextX]) {
				dfsRecursion(nextY, nextX);
			}
	}
}

int graphSearchAll() {
	int result = 0;

	for (int y = 0; y < N; y++)
		for (int x = 0; x < M; x++) {
			if (adj[y][x] && !visited[y][x]) {
				result++;
				bfs(y, x);
				//dfsStack(y, x);
				//dfsRecursion(y, x);
			}
		}

	return result;
}

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

	while (tc--) {
		cin >> M >> N >> K;

		memset(adj, false, sizeof(adj));
		memset(visited, false, sizeof(visited));

		while (K--) {
			int x, y;
			cin >> x >> y;
			adj[y][x] = true;
		}

		cout << graphSearchAll() << endl;
	}

	return 0;
}

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

원숭이의 좌표와 말처럼 이동할 수 있는 횟수가 몇번 남았는지에 대한 정보, 이동한 횟수를 queue에 담아서 bfs를 수행하면 원하는 결과를 얻을 수 있다.

한가지 유의할 점은 말처럼 이동할 경우 장애물을 뛰어넘을 수 있기 때문에 이미 방문한 좌표라도 말처럼 이동할 수 있는 횟수가 남아있느냐 남아있지 않느냐에 따라 결과값이 달라지게 된다.

따라서, 중복탐색을 피하기 위한 visited 배열을 좌표 정보만 담은 2차원 배열이 아닌, 말처럼 이동한 횟수까지 포함하는 3차원 배열로 선언해야 한다.

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

int K, H, W;
int board[200][200];
bool visited[200][200][31];

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

struct Pos {
	int y;
	int x;
};

int bfs() {
	queue<pair<pair<Pos, int>, int>> q;
	q.push({ { {0,0}, K }, 0 });
	visited[0][0][K] = true;

	while (!q.empty()) {
		int hereY = q.front().first.first.y;
		int hereX = q.front().first.first.x;
		int horse = q.front().first.second;
		int move = q.front().second;

		q.pop();

		if (hereY == H - 1 && hereX == W - 1)
			return move;

		for (int i = 0; i < 12; i++) {
			if (horse <= 0 && i < 8) continue;
			int nextY = hereY + dy[i];
			int nextX = hereX + dx[i];
			if (nextY >= 0 && nextY < H && nextX >= 0 && nextX < W) {
				if (i < 8) {
					if (board[nextY][nextX] == 0 && !visited[nextY][nextX][horse - 1]) {
						q.push({ {{nextY, nextX}, horse - 1 }, move + 1 });
						visited[nextY][nextX][horse - 1] = true;
					}
				}
				else {
					if (board[nextY][nextX] == 0 && !visited[nextY][nextX][horse]) {
						q.push({ {{nextY, nextX}, horse}, move + 1 });
						visited[nextY][nextX][horse] = true;
					}
				}
			}
		}
	}

	return -1;
}
int main(void) {
	cin >> K >> W >> H;

	for (int i = 0; i < H; i++)
		for (int j = 0; j < W; j++)
			cin >> board[i][j];

	cout << bfs() << endl;

	return 0;
}

[문제 링크]

간단한 bfs 문제였다.

수빈이가 +1, -1로 이동하는 경우와, *2로 이동하는 경우에 대해서 bfs를 돌려서 동생을 찾는 가장 빠른 방법을 찾으면 된다.

수빈이가 이동하는 경로를 저장하기 위해 queue에 현재 위치와 그동안 이동했던 경로를 담은 queue를 pair 자료구조에 담았다.

한가지 함정이 있다면, 수빈이가 동생보다 앞에 있을 경우, +1과 *2로 이동하게 되면 반드시 더 멀어지게 되기 때문에 -1로만 이동하게 된다.

극단적인 예로 만약 수빈이가 100000에 위치해 있고, 동생이 0에 위치해 있는 경우 수빈이의 이동경로는 100000 99999 99998 .... 0 이 된다. 이 경로를 queue에 전부 담게 되면 시간복잡도 및 공간복잡도가 매우 커지게 된다.

따라서 시작지점이 수빈이가 동생보다 앞일 경우, bfs를 수행하지 않고 -1로 이동하는 경로를 출력하도록 구현하였다.

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

bool visited[100001];

queue<int> bfs(int N, int K) {
	queue < pair<int, queue<int>>> q;
	q.push({ N, queue<int>({N}) });
	visited[N] = true;

	while (!q.empty()) {
		int here = q.front().first;
		queue<int> route = q.front().second;
		q.pop();

		if (here == K) return route;

		for (int i = 0; i < 3; i++) {
			int next;
			if (i == 0) next = here + 1;
			else if (i == 1) next = here - 1;
			else next = here * 2;

			if (next >= 0 && next <= 100000 && !visited[next]) {
				queue<int> temp = route;
				temp.push(next);
				q.push({ next, temp });
				visited[next] = true;
			}
		}
	}

	return queue<int>();
}

int main(void) {
	int N, K;
	cin >> N >> K;

	if (N >= K) {
		cout << N - K << endl;
		while (N >= K)
			cout << N-- << ' ';
	}
	else {
		queue<int> result = bfs(N, K);

		cout << result.size() - 1 << endl;
		while (!result.empty()) {
			cout << result.front() << ' ';
			result.pop();
		}
	}

	return 0;
}

[문제 링크]

간단해보이지만 함정이 하나 있는 문제였다.

치즈가 공기와 접촉하는지 확인하기 위해 치즈 기준 동서남북 방향에 0이 있는지 체크하고 0이 두군데 이상 있다면 공기와 접촉하고 있다고 단정 지을 수 있는데, 치즈로 둘러 쌓인 내부의 0은 공기가 통하지 않기 때문에 이를 제외시켜줘야 한다.

따라서, 치즈를 녹이기 전에 {0, 0} 좌표를 시작으로 BFS를 수행하여 실제로 공기가 통하는 좌표를 먼저 마킹했다.

그 다음 전체 판을 탐색하여 공기와 접해있는 면이 2개 이상인 치즈를 녹이는 방식으로 구현하였다.

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

int N, M, cheezeCnt = 0;
int board[101][101];
bool isAir[101][101];

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

void markingAir() {
	queue<pair<int, int>> q;
	memset(isAir, false, sizeof(isAir));

	q.push({ 0,0 });
	isAir[0][0] = true;

	while (!q.empty()) {
		int hereY = q.front().first;
		int hereX = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nearY = hereY + dy[i];
			int nearX = hereX + dx[i];
			if (nearY >= 0 && nearY < N && nearX >= 0 && nearX < M) {
				if (board[nearY][nearX] == 0 && !isAir[nearY][nearX]) {
					q.push({ nearY, nearX });
					isAir[nearY][nearX] = true;
				}
			}
		}
	}
}

void meltCheeze() {
	int temp[101][101];

	memcpy(temp, board, sizeof(board));

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (temp[i][j] == 1) {
				int air = 0;

				for (int k = 0; k < 4; k++) {
					int nearY = i + dy[k];
					int nearX = j + dx[k];
					if (isAir[nearY][nearX])
						air++;
				}

				if (air >= 2) {
					board[i][j] = 0;
					cheezeCnt--;
				}
			}
		}
	}
}

int getAllMeltCheezeTime() {
	int time = 0;

	while (cheezeCnt) {
		markingAir();
		meltCheeze();
		time++;
	}

	return time;
}

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

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++) {
			int n;
			cin >> n;
			board[i][j] = n;
			if (board[i][j] == 1)
				cheezeCnt++;
		}

	cout << getAllMeltCheezeTime() << endl;

	return 0;
}