[BAEKJOON] 1600, 2146, 2636

※ 소스코드는 각 문제 설명 하단에 <더보기>를 통해 확인하실 수 있습니다.

 

[gold 3, 1600 말이 되고픈 원숭이] - 너비우선탐색(BFS)

원숭이가 K번 움직이는 방문 배열을 3차원 배열을 활용해서 풀어나가는 것에 유의하자.

 

원숭이의 움직임은 다음과 같은 순서로 진행된다.

1) K번 움직이지 않았다면, 점프 BFS

2) 상하좌우 BFS

3) 도착지점에 도착했을 시, 카운팅 값 출력
4) 도착하지 못했을 시, -1 출력

#include <iostream>
#include <queue>
#pragma warning(disable:4996)

using namespace std;

#define MAX 201

int H, W, K;
int map[MAX][MAX];
bool visit[MAX][MAX][31];

typedef struct data {
	int y, x, c, k;
}Data;

queue<Data> q;

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

int udy[] = { -1,-2,-2,-1,1,2,2,1 };
int udx[] = { -2,-1,1,2,2,1,-1,-2 };

bool range(int y, int x) {
	return y<0 || x<0 || y>H - 1 || x>W - 1;
}


void moveMonkey(int y, int x, int c, int k) {
	if (!range(y, x) && !map[y][x] && !visit[y][x][k]) {
		visit[y][x][k] = true;
		q.push({ y, x, c, k });
	}
}

int main() {
	scanf("%d", &K);
	scanf("%d %d", &W, &H);
	for (int i = 0; i < H; i++)
		for (int j = 0; j < W; j++)
			scanf("%d", &map[i][j]);

	q.push({ 0, 0, 0, 0 });
	visit[0][0][0] = true;
	while (!q.empty()) {
		Data out = q.front(); q.pop();
		if (out.y == H - 1 && out.x == W - 1) {
			printf("%d", out.c);
			return 0;
		}
		if (out.k < K) {
			for (int ud = 0; ud < 8; ud++) {
				int ny = out.y + udy[ud];
				int nx = out.x + udx[ud];
				int nc = out.c + 1;
				int nk = out.k + 1;
				moveMonkey(ny, nx, nc, nk);
			}
		}
		for (int d = 0; d < 4; d++) {
			int ny = out.y + dy[d];
			int nx = out.x + dx[d];
			int nc = out.c + 1;
			int nk = out.k;
			moveMonkey(ny, nx, nc, nk);
		}
	}
	printf("-1");
}

 

[gold 3, 2146 다리 만들기] - 너비우선탐색(BFS)

전형적인 BFS지만, 문제 조건에 의해 설계를 잘 해놓아야 한다. 풀이 진행은 다음과 같다.

1) 섬을 찾는다

2) 하나의 섬을 찾았을 때, 그 섬으로부터 다른 섬까지 가장 빠른 경로를 카운팅한다.

3) 2)의 결과 값을 비교한다

4) 다음 섬이 존재하지 않을 때까지 1) ~ 3)을 반복한다.

 

1)과 2)의 큐와 방문배열을 각각 두고 진행하면 깔끔한 진행을 할 수 있다. 시작 점을 모든 큐에 삽입하는 것에 잊지말고(17%에서 오류가 나면 보통 시작점이 추가되지 않은 경우), 1)에서 섬을 찾을 때 2)의 방문배열을 함께 기록하는 것을 놓치지 않는 것에 유의하자.

#include <iostream>
#include <queue>
#include <vector>
#include <string.h>
#include <algorithm>
#pragma warning(disable:4996)

using namespace std;

#define MAX 101
int N, island_ea, answer = 987654321;

int map[MAX][MAX];
bool visit[MAX][MAX] = { 0, };
bool island[MAX][MAX] = { 0, };

typedef struct data {
	int y, x, c;
}Data;

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

bool range(int y, int x) {
	return y<0 || x<0 || y>N - 1 || x>N - 1;
}

int buildBridge(queue<Data> q) {
	while (!q.empty()) {
		Data out = q.front(); q.pop();
		for (int d = 0; d < 4; d++) {
			int ny = out.y + dy[d];
			int nx = out.x + dx[d];
			int nc = out.c + 1;
			if (!range(ny, nx) && !visit[ny][nx]) {
				if (map[ny][nx]) {
					return out.c;
				}
				visit[ny][nx] = true;
				q.push({ ny, nx, nc });
			}
		}
	}
	return 987654321;
}

void findIsland() {
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++) {
			if (map[i][j] && !island[i][j]) {
				queue<Data> q;
				queue<Data> nq;
				q.push({ i, j, 0 });
				nq.push({ i, j, 0 });
				
				memset(visit, 0, sizeof visit);
				visit[i][j] = true;
				island[i][j] = true;

				while (!q.empty()) {
					Data out = q.front(); q.pop();
					for (int d = 0; d < 4; d++) {
						int ny = out.y + dy[d];
						int nx = out.x + dx[d];
						if (!range(ny, nx) && map[ny][nx] && !island[ny][nx]) {
							visit[ny][nx] = true;
							island[ny][nx] = true;
							q.push({ ny, nx, 0 });
							nq.push({ ny, nx, 0 });
						}
					}
				}
				 
				int result = buildBridge(nq);
				answer = min(answer, result);
				
				island_ea += 1;
			}
		}
}
int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			scanf("%d", &map[i][j]);

	findIsland();

	printf("%d", answer);
}

 

[gold 4, 2636 치즈] - 너비우선탐색(BFS)

복잡하게 생각할 필요 없이 간단하게 BFS 설계를 세우고 진행하면 된다. 가장 큰 힌트는, 방문배열을 초기화 할 필요가 없다는 것이다. 설계는 다음과 같이 진행했다.

 

1) 첫 치즈를 찾는다

2) 치즈를 확인한다

3) 치즈가 있으면, 해당 치즈들을 복사하고 치즈를 녹인다

4) 복사한 치즈를 시작점으로 2) ~ 3)을 반복한다.

5) 4)가 진행될 때 시간초를 센다

 

치즈를 찾는 행위는 동일하므로 녹일 치즈와 시작점으로 할 치즈, 두개의 큐를 잘 활용해서 풀어주도록 하자.

#include <iostream>
#include <string.h>
#include <queue>
#pragma warning(disable:4996)
using namespace std;

#define MAX 101
int H, W, prevCheese;
int map[MAX][MAX];
bool visit[MAX][MAX] = { 0, };
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };

typedef struct data {
	int y, x;
}Data;

queue <Data> cheese;
queue <Data> q;

bool range(int y, int x) {
	return y<0 || x<0 || y>H - 1 || x>W - 1;
}

void findCheese() {
	while (!q.empty()) {
		Data out = q.front(); q.pop();
		for (int d = 0; d < 4; d++) {
			int ny = out.y + dy[d];
			int nx = out.x + dx[d];
			if (!range(ny, nx) && !visit[ny][nx]) {
				visit[ny][nx] = true;
				if (map[ny][nx]) {
					cheese.push({ ny, nx });
				}
				else q.push({ ny, nx });
			}
		}
	}
}
int main() {
	scanf("%d %d", &H, &W);
	for (int i = 0; i < H; i++)
		for (int j = 0; j < W; j++)
			scanf("%d", &map[i][j]);

	// 첫 치즈를 찾는다
	q.push({ 0, 0 });
	findCheese();

	int answer = 0;
	// 치즈를 확인한다
	while (!cheese.empty()) {
		// 치즈가 있으면 치즈를 복사하고 녹인다
		q = cheese;
		prevCheese = cheese.size();
		while (!cheese.empty()) {
			Data out = cheese.front(); cheese.pop();
			map[out.y][out.x] = 0;
		}
		// 치즈를 찾는다
		findCheese();
		// 시간초를 센다
		answer += 1;
	}
	printf("%d\n%d", answer, prevCheese);
}