0x09
2146 | 다리 만들기
처음 버전
#include <bits/stdc++.h>
using namespace std;
int n, island = 2, ans = INT_MAX;
int board[100][100], dist[100][100];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
void bfs() {
queue<pair<int, int> > q;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
dist[i][j] = -1;
if (board[i][j] == island) {
q.push({i, j});
dist[i][j] = 0;
}
}
}
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int dir = 0; dir < 4; ++dir) {
int nx = x + dx[dir], ny = y + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (board[nx][ny] == island || dist[nx][ny] != -1) continue;
if (board[nx][ny] > 0) {
ans = min(ans, dist[x][y]);
return;
}
q.push({nx, ny});
dist[nx][ny] = dist[x][y] + 1;
}
}
}
void mark(int i, int j) {
queue<pair<int, int> > q;
q.push({i, j});
board[i][j] = island;
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int dir = 0; dir < 4; ++dir) {
int nx = x + dx[dir], ny = y + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (board[nx][ny] == island || !board[nx][ny]) continue;
q.push({nx, ny});
board[nx][ny] = island;
}
}
++island;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) cin >> board[i][j];
}
// 각 구역을 칠해놓고
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == 1) mark(i, j);
}
}
// 각 섬마다 bfs
while (island > 1) {
bfs();
--island;
}
cout << ans;
}맞긴 맞았다. 근데 개선의 여지가 있었다.
지금은 각 섬마다 bfs를 하는데, 동시에 bfs를 하도록 구현할 수 있다.
개선 버전
#include <bits/stdc++.h>
using namespace std;
int n, island = 2, ans = INT_MAX;
int board[100][100], dist[100][100];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
void bfs() {
queue<pair<int, int> > q;
for (int i = 0; i < n; ++i) fill(dist[i], dist[i] + n, -1);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j]) {
q.push({i, j});
dist[i][j] = 0;
}
}
}
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int dir = 0; dir < 4; ++dir) {
int nx = x + dx[dir], ny = y + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (board[nx][ny] == board[x][y]) continue;
if (board[nx][ny] && board[nx][ny] != board[x][y]) {
ans = min(ans, dist[nx][ny] + dist[x][y]);
}
if (!board[nx][ny] && dist[nx][ny] == -1) { // 바다를 처음 만났다면
board[nx][ny] = board[x][y];
dist[nx][ny] = dist[x][y] + 1;
q.push({nx, ny});
}
}
}
}
void mark(int i, int j) {
queue<pair<int, int> > q;
q.push({i, j});
board[i][j] = island;
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int dir = 0; dir < 4; ++dir) {
int nx = x + dx[dir], ny = y + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (board[nx][ny] == island || !board[nx][ny]) continue;
q.push({nx, ny});
board[nx][ny] = island;
}
}
++island;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) cin >> board[i][j];
}
// 각 구역을 칠해놓고
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == 1) mark(i, j);
}
}
// bfs
bfs();
cout << ans;
}- 처음에 모든 섬의 육지 칸을 큐에 다 넣고 시작한다.
즉, 각 섬에서 동시에 바다로 확장해 나가는 구조다. - 외곽 지역이 바다(board[nx][ny] == 0)라면,
큐에 넣고 dist[nx][ny] = dist[x][y] + 1로 갱신하며 확장해 나간다.
이때 중요한 건 "이 바다가 어떤 섬으로부터 왔는지" 기록해야 한다는 것. - 그래서 바다를 방문할 때는
board[nx][ny] = board[x][y]로 섬 번호를 전파해줘야 한다.
그래야 이후에 "서로 다른 섬이 만났는지"를 판단할 수 있다. - 만약 인접한 칸이 육지이고,
board[nx][ny] != board[x][y]라면?
다른 섬이랑 만난 거다! → 이때 다리 길이를 min으로 갱신
13549 | 숨바꼭질 3
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100001;
int dist[MAX];
deque<int> dq;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
fill(dist, dist + MAX, -1);
dist[n] = 0;
dq.push_front(n);
while (!dq.empty()) {
int x = dq.front();
dq.pop_front();
if (x == k) break;
int nx;
// 순간이동
nx = x * 2;
if (nx < MAX && dist[nx] == -1) {
dist[nx] = dist[x];
dq.push_front(nx);
}
// 걷기
for (int dx : {-1, 1}) {
nx = x + dx;
if (nx >= 0 && nx < MAX && dist[nx] == -1) {
dist[nx] = dist[x] + 1;
dq.push_back(nx);
}
}
}
cout << dist[k];
}0-1 BFS
이건 0-1 BFS문제라고 한다! 이전 BFS 문제들은 가중치가 모두 같았다.
이전엔 어떤 이동이든 시간이 모두 같았는데, 이 문제는 순간이동은 0초, 걷기는 1초로 걸리는 시간이 다르다.
그래서 전과 같이 q에 순차적으로 push를 하게 되면 오답이 된다.
이는 dq를 사용하면 간단히 해결할 수 있다.
가중치가 0인 것(순간 이동)은 앞쪽에 push하고, 1인 것(걷기)은 뒤쪽에 push해서
똑같은 시점에 push를 해도 처리의 우선순위를 다르게 만들면 된다.
1600 | 말이 되고픈 원숭이
#include <bits/stdc++.h>
using namespace std;
int K, W, H;
int board[200][200];
int dist[200][200][31];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
int hdx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int hdy[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
queue<tuple<int, int, int> > q;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> K >> W >> H;
for (int i = 0; i < H; ++i) {
for (int j = 0; j < W; ++j) {
cin >> board[i][j];
}
}
q.push({0, 0, 0});
dist[0][0][0] = 1;
while (!q.empty()) {
auto [x, y, cnt] = q.front();
q.pop();
if (x == H - 1 && y == W - 1) {
cout << dist[x][y][cnt] - 1;
return 0;
}
for (int d = 0; d < 4; ++d) {
int nx = x + dx[d], ny = y + dy[d];
if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
if (board[nx][ny] || dist[nx][ny][cnt]) continue;
q.push({nx, ny, cnt});
dist[nx][ny][cnt] = dist[x][y][cnt] + 1;
}
if (cnt == K) continue;
for (int d = 0; d < 8; ++d) {
int nx = x + hdx[d], ny = y + hdy[d];
if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
if (board[nx][ny] || dist[nx][ny][cnt + 1]) continue;
q.push({nx, ny, cnt + 1});
dist[nx][ny][cnt + 1] = dist[x][y][cnt] + 1;
}
}
cout << -1;
}이전에 상태값을 들고 가야 했던 벽 부수기 문제를 풀었어서
아이디어를 떠올리는 건 쉬웠다.
근데 인접한 곳 이동의 경우 if (board[nx][ny] || dist[nx][ny][cnt]) continue; 조건을 써야 하고
말 움직임 이동인 경우 if (board[nx][ny] || dist[nx][ny][cnt + 1]) continue; 조건을 써야 하는데
위에 걸 그대로 복붙해서 쓰다가 말 이동의 경우도 if (board[nx][ny] || dist[nx][ny][cnt]) continue; 조건을 써버리는 바람에 메모리 초과가 났었다..
처음엔 내가 선언한 배열이 너무 커서 메모리 제한을 넘기는 줄 알았는데 전혀 아니었다.
메모리 제한은 256MB. 지금 내가 선언한 메모리는 크게 int [200][200][31], int [200][200].
int 4byte x 200 x 200 x 31 = 4,960,000
4,960,000 / 100만 = 약 4.96mb
메모리 제한이 256mb인데 이는 엄청엄청 넉넉한 메모리였다.
그니까 메모리 초과는 큐에서 일어나는 게 분명했던 것.
휴.. 메모리 계산 시간복잡도 계산 연습 많이 해야겠다..
그리고 처음에 int dist[200][200][30]으로 선언했었는데 그럼 안 됐다 !! 왜냐면 k는 30까지 될 수 있고 그럼 dist[i][j][30]에 값이 저장될 때도 있을텐데 out of bounds가 됐던 것!
좋게 한 2~3씩 더 늘려서 선언하자.. 딱 맞게 선언하지 말고.. 괜히 OOB 될 수 있으니까
0-1 BFS vs 상태 기반 BFS
앞에서 0-1 BFS를 풀어서인지 이 문제도 0-1 BFS 문제인 거 아닌가 헷갈렸다. 왜냐면 인접한 좌표 방문보다 말의 이동이 좌표를 훨씬 빨리 이동하는 게 될 거 같았기 때문이다.
그런데 핵심은 이동하는 데 시간이 같냐 vs 다르냐였다.
다른 경우 0-1 BFS 이고 같은 경우는 그저 상태를 나눠서 일반 BFS를 해주면 됐다.
챗지피티 답변
"이 문제를 0-1 BFS로 풀어야 할까, 상태를 나눠서 일반 BFS로 풀어야 할까?"
👉 이건 BFS류 문제의 진짜 핵심 감각을 요구하는 질문이야.
아래에 구조화해서 완전히 정리해줄게.
🔍 1. 0-1 BFS vs 상태 기반 BFS, 개념 차이
| 구분 | 설명 |
|---|---|
| 0-1 BFS | 간선에 가중치가 0 또는 1일 때 → 덱으로 가중치 처리 |
| 상태 기반 BFS (벽 부수기 등) | 행동 횟수/사용 여부/조건이 상태를 나누는 기준일 때 → 2차원 이상 dist 배열 필요 |
✅ 이 문제(말처럼 이동)는 가중치가 다른 게 아님!
- 말 이동이 시간이 0이거나 더 빠른 게 아니야
- 그냥 **횟수 제한이 있는 "특수한 방향 이동"**일 뿐이야
- 모든 이동은 동등하게 1초 걸림
→ 즉, 가중치는 모두 1
💡 그래서:
👉 말 이동이 "빠른 것처럼 보여도"
가중치 1짜리 다른 방향일 뿐이기 때문에 0-1 BFS가 아님
🧠 언제 0-1 BFS를 쓰는가?
같은 노드라도 더 빨리 도달할 수 있는 간선이 '가중치 0'이라서 먼저 처리되어야 할 때
예시:
- 숨바꼭질 3 (순간이동 0초, 걷기 1초)
- 간선이 0, 1로 주어지는 그래프 최단거리
👉 덱을 써야 "빠른 것부터 먼저" 꺼내서 처리할 수 있음
🧠 언제 상태 기반 BFS를 쓰는가?
같은 좌표라도 "벽을 부쉈느냐", "말을 몇 번 썼느냐"에 따라 다르게 처리해야 할 때
예시:
- 벽 부수고 이동하기 →
dist[x][y][벽부숨 여부] - 말처럼 이동하기 →
dist[x][y][말 사용 횟수] - 열쇠 사용 여부, 변신 여부, 체력 상태 등
🎯 정리! 구분법
| 질문 | 답변 |
|---|---|
| 이동에 따라 시간이 다르게 걸리는가? (예: 0초, 1초) | ✅ → 0-1 BFS |
| 이동 시간은 같지만 이동 방식의 조건이 다른가? | ✅ → 상태 기반 BFS |
| 특정 행동을 몇 번 했는지 여부가 중요하다 | ✅ → 상태 기반 BFS |
| 간선마다 0, 1 가중치가 존재한다 | ✅ → 0-1 BFS |
✨ 요 문제에 적용하면?
- 말 이동이 아무리 "멀리 가는 것처럼 보여도"
1턴에 1번만 가능하고 시간도 1 증가하므로
➤ 상태 기반 BFS가 맞다!
🧠 기억용 한 줄 요약
“행동의 조건에 따라 상태가 나뉘면 상태 BFS”,
“행동 자체가 빠르면 0-1 BFS”
