백준 1194번 달이 차오른다, 가자

https://www.acmicpc.net/status?user_id=skaduddn&problem_id=1194&from_mine=1

채점 현황

 

 

 

 

 

 

<접근방법>

탐색 문제입니다.

상태에 대한 방문 관리와 키 관리가 포인트인 거 같습니다.

비트마스킹을 모르는 상태에서는 배열 크기를 늘리고 구현 노가다를 해서 풀었습니다.

후에 검색을 통해 비트마스킹으로 풀었습니다.

 

 

비트마스킹을 모르시는 분들이 읽으면 좋을 거 같습니다.

https://yabmoons.tistory.com/102

---

 

 

 

<코드>

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

struct point {
	int y, x, cnt;
	int a, b, c, d, e, f;
};

int n, m, sy, sx;
char map[52][52];
int dy[4] = { 1, -1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
int visit[51][51][2][2][2][2][2][2];

int bfs() {
	queue<point> q;

	q.push({ sy, sx, 0, 0, 0, 0, 0, 0, 0});
	visit[sy][sx][0][0][0][0][0][0] = 1;

	while (!q.empty()) {
		point t = q.front();
		q.pop();

		if (map[t.y][t.x] == '1') {
			return t.cnt;
		}

		for (int i = 0; i < 4; i++) {
			int ty = t.y + dy[i];
			int tx = t.x + dx[i];
			int a = t.a, b = t.b, c = t.c, d = t.d, e = t.e, f = t.f;

			if (ty < 0 || ty >= n || tx < 0 || tx >= m) continue;
			if (map[ty][tx] == '#') continue;
			if (visit[ty][tx][t.a][t.b][t.c][t.d][t.e][t.f] == 1) {
				continue;
			}

			if (map[ty][tx] == 'A' && a == 0) continue;
			if (map[ty][tx] == 'B' && b == 0) continue;
			if (map[ty][tx] == 'C' && c == 0) continue;
			if (map[ty][tx] == 'D' && d == 0) continue;
			if (map[ty][tx] == 'E' && e == 0) continue;
			if (map[ty][tx] == 'F' && f == 0) continue;

			if (map[ty][tx] == 'a') {
				a = 1;
			}
			else if (map[ty][tx] == 'b') {
				b = 1;
			}
			else if (map[ty][tx] == 'c') {
				c = 1;
			}
			else if (map[ty][tx] == 'd') {
				d = 1;
			}
			else if (map[ty][tx] == 'e') {
				e = 1;
			}
			else if (map[ty][tx] == 'f') {
				f = 1;
			}

			q.push({ty, tx, t.cnt + 1, a, b, c, d, e, f});
			visit[ty][tx][a][b][c][d][e][f] = 1;
		}
	}
	return -1;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			if (map[i][j] == '0') {
				sy = i; sx = j;
			}
		}
	}

	cout << bfs() << '\n';

	return 0;
}

 

---

 

 

//비트마스킹
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

struct point {
	int y, x, cnt, key;
};

int n, m, sy, sx;
char map[52][52];
int dy[4] = { 1, -1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
bool visit[51][51][1 << 6];

bool check_key(int key, char c) {
	int tmp = key & (1 << (c - 'A'));
	if (tmp == 0) return false;
	return true;
}

int bfs() {
	queue<point> q;

	q.push({ sy, sx, 0, 0});
	visit[sy][sx][0] = true;

	while (!q.empty()) {
		point t = q.front();
		q.pop();

		if (map[t.y][t.x] == '1') {
			return t.cnt;
		}

		for (int i = 0; i < 4; i++) {
			int ty = t.y + dy[i];
			int tx = t.x + dx[i];
			int tkey = t.key;
			bool suc = true;

			if (ty < 0 || ty >= n || tx < 0 || tx >= m) continue;
			if (map[ty][tx] == '#') continue;
			if (visit[ty][tx][t.key]) continue;

			if ('a' <= map[ty][tx] && map[ty][tx] <= 'f') {
				tkey = t.key | (1 << map[ty][tx] - 'a');
			}
			else if ('A' <= map[ty][tx] && map[ty][tx] <= 'F') {
				if (!check_key(t.key, map[ty][tx])) {
					suc = false;
				}
			}
			if (suc) {
				visit[ty][tx][tkey] = true;
				q.push({ty, tx, t.cnt + 1, tkey});
			}
		}
	}
	return -1;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			if (map[i][j] == '0') {
				sy = i; sx = j;
			}
		}
	}

	cout << bfs() << '\n';

	return 0;
}

 

 

 

 

---

 

 

<느낀 점>

-비트마스킹