13335 | 트럭
#include <bits/stdc++.h>
using namespace std;
int n, w, L, ans;
int truck[1000];
void run() {
queue<int> bridge;
int curl_l = 0, cur = 0;
for (int i = 0; i < w; ++i) bridge.push(0);
while (cur < n) {
curl_l -= bridge.front();
bridge.pop();
if (curl_l + truck[cur] <= L) {
bridge.push(truck[cur]);
curl_l += truck[cur++];
} else {
bridge.push(0);
}
++ans;
}
ans += w;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> w >> L;
for (int i = 0; i < n; ++i) cin >> truck[i];
run();
cout << ans;
}트럭은 무조건 1초에 거리 1만큼 전진한다.
이때 새로운 트럭이 다리에 올라갈 수 있다면 진입시키고,
불가능하다면 0을 큐에 넣어 다리 위 공간을 유지한다.
0을 넣어주지 않으면 트럭이 들어오지 못하고 있는 동안에도 앞 트럭과 뒷 트럭 간의 간격이 벌어지지 않기 때문에,
트럭 간 거리 유지를 위해 반드시 0을 넣어줘야 한다.
16985 | Maaaaaaaaaze
ver1
#include <bits/stdc++.h>
using namespace std;
int board_raw[5][5][5]; // 입력 원본
int rotated[5][4][5][5]; // [층][회전][i][j]
int board[5][5][5]; // 최종 큐브
int r[5], p[5], ans = INT_MAX;
bool isused[5];
int du[6] = {1, -1, 0, 0, 0, 0};
int dx[6] = {0, 0, 1, 0, -1, 0};
int dy[6] = {0, 0, 0, -1, 0, 1};
void rotate_layer(int dst[5][5], int src[5][5]) {
for (int i = 0; i < 5; ++i)
for (int j = 0; j < 5; ++j) dst[j][4 - i] = src[i][j];
}
void preprocess() {
for (int n = 0; n < 5; ++n) {
// 0도 회전
for (int i = 0; i < 5; ++i)
for (int j = 0; j < 5; ++j) rotated[n][0][i][j] = board_raw[n][i][j];
// 90, 180, 270도 회전
for (int k = 1; k < 4; ++k) rotate_layer(rotated[n][k], rotated[n][k - 1]);
}
}
void bfs() {
if (board[0][0][0] == 0 || board[4][4][4] == 0) return;
queue<tuple<int, int, int>> q;
int dist[5][5][5] = {};
q.push({0, 0, 0});
dist[0][0][0] = 1;
while (!q.empty()) {
auto [u, x, y] = q.front();
q.pop();
if (u == 4 && x == 4 && y == 4) {
ans = min(ans, dist[u][x][y] - 1);
if (ans == 12) {
cout << 12;
exit(0);
}
return;
}
if (dist[u][x][y] > ans) continue;
for (int i = 0; i < 6; ++i) {
int nu = u + du[i], nx = x + dx[i], ny = y + dy[i];
if (nu < 0 || nu >= 5 || nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
if (dist[nu][nx][ny] || board[nu][nx][ny] == 0) continue;
dist[nu][nx][ny] = dist[u][x][y] + 1;
q.push({nu, nx, ny});
}
}
}
void simulation() {
for (int i = 0; i < 5; ++i) {
int pi = p[i];
int ri = r[i];
for (int x = 0; x < 5; ++x)
for (int y = 0; y < 5; ++y) board[i][x][y] = rotated[pi][ri][x][y];
}
bfs();
}
void dfs_r(int k) {
if (k == 5) {
simulation();
return;
}
for (int i = 0; i < 4; ++i) {
r[k] = i;
dfs_r(k + 1);
}
}
void dfs_p(int k) {
if (k == 5) {
dfs_r(0);
return;
}
for (int i = 0; i < 5; ++i) {
if (isused[i]) continue;
isused[i] = 1;
p[k] = i;
dfs_p(k + 1);
isused[i] = 0;
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
for (int n = 0; n < 5; ++n)
for (int i = 0; i < 5; ++i)
for (int j = 0; j < 5; ++j) cin >> board_raw[n][i][j];
preprocess(); // 회전 상태 미리 계산
dfs_p(0); // 쌓는 순서 + 회전 순서 조합 탐색
if (ans == INT_MAX)
cout << -1;
else
cout << ans;
}ver2
#include <bits/stdc++.h>
using namespace std;
int board[4][5][5][5];
int maze[5][5][5];
int dz[6] = {1, -1, 0, 0, 0, 0};
int dx[6] = {0, 0, 1, 0, -1, 0};
int dy[6] = {0, 0, 0, -1, 0, 1};
int ans = INT_MAX;
bool OOB(int nz, int nx, int ny) {
return (nz < 0 || nz >= 5 || nx < 0 || nx >= 5 || ny < 0 || ny >= 5);
}
void bfs() {
queue<tuple<int, int, int>> q;
int dist[5][5][5] = {};
// 입구 (0, 0, 0) 출구 (4, 4, 4)
if (!maze[0][0][0] || !maze[4][4][4]) return;
q.push({0, 0, 0});
dist[0][0][0] = 1;
while (!q.empty()) {
auto [z, x, y] = q.front();
q.pop();
if (dist[z][x][y] >= ans) continue;
for (int d = 0; d < 6; ++d) {
int nz = z + dz[d], nx = x + dx[d], ny = y + dy[d];
if (OOB(nz, nx, ny) || !maze[nz][nx][ny] || dist[nz][nx][ny])
continue;
if (nz == 4 && nx == 4 && ny == 4) {
ans = min(ans, dist[z][x][y]);
if (ans == 12) {
cout << 12;
exit(0);
}
return;
}
q.push({nz, nx, ny});
dist[nz][nx][ny] = dist[z][x][y] + 1;
}
}
}
void run() {
int order[5] = {0, 1, 2, 3, 4};
do {
for (int mask = 0; mask < 1024; ++mask) {
int tmp = mask;
for (int i = 0; i < 5; ++i) {
int d = tmp % 4;
memcpy(maze[i], board[d][order[i]], sizeof maze[i]);
tmp /= 4;
}
bfs();
}
} while (next_permutation(order, order + 5));
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
// 입력
for (int i = 0; i < 5; ++i) {
for (int r = 0; r < 5; ++r) {
for (int c = 0; c < 5; ++c) cin >> board[0][i][r][c];
}
// 회전 미리 저장
for (int d = 1; d < 4; ++d) {
for (int r = 0; r < 5; ++r) {
for (int c = 0; c < 5; ++c)
board[d][i][4 - c][r] = board[d - 1][i][r][c];
}
}
}
run();
if (ans == INT_MAX)
cout << -1;
else
cout << ans;
}처음에 dfs를 직접 해서 조합을 구해줬는데
바킹독님 풀이를 보니 next_permutation 사용, 4진수 마스킹 활용으로 각각 판을 쌓는 순서, 회전 각도 조합을 구해주셨다.
이러니 훨씬 코드가 간결해졌다.
그리고 챗지피티가 더 최적화할 수 있도록 입구/출구가 이미 막혀있다면 조기 탈출, ans가 이미 최솟값이라면(12) 조기 탈출하도록 추천해줘서
그렇게 더 적용해줬다.
주의
이 문제에선 미로를 들어갈 수 있으면 1 없으면 0이다!!
이제껏 bfs 문제에서 벽이 1로 주어졌어서 그런지 처음에 무심코 조건을 1이면 갈 수 없다고 줘버렸었다;;
문제에서 값을 항상 잘 확인!!! 다른 문제들도 보면 행을 x로 열을 y로 주는 경우가 있음. 보통 반대인데도. 이럴 때 평소처럼 cin >> x >> y;로 받으면 큰일 나는 거
그리고 인덱스도 0~n-1이 아니라 1~n로 주는 경우도 있고. 이러면 또 OOB 체크에서 (x < 0 || x >= n)으로 했다가 큰일 나는 거. 애초에 --x;를 해주거나 (x < 1 || x > n) 으로 해줘야 함.
꼭 꼭 문제에서 주어진 경우와 값의 대응을 확실히 짚고 가자!!
아 그리고 4진수로 경우의 수 구할 때
for (int mask = 0; mask < 1024; ++mask) {
int tmp = mask;
for (int i = 0; i < 5; ++i) {
int d = tmp % 4;
memcpy(maze[i], board[d][order[i]], sizeof maze[i]);
tmp /= 4;
}
bfs();
}여기서 tmp 안 쓰고
for (int mask = 0; mask < 1024; ++mask) {
for (int i = 0; i < 5; ++i) {
int d = mask % 4;
memcpy(maze[i], board[d][order[i]], sizeof maze[i]);
mask /= 4;
}
bfs();
}for문에 쓰이는 mask 값을 /=4를 해줘버려서 무한 루프를 돌았었다;;;
for문에 쓰이는 값을 건드려 버리진 않는지 꼭꼭 주의
14503 | 로봇 청소기
#include <bits/stdc++.h>
using namespace std;
#define GO 0
#define WALL 1
#define VISIT -1
int N, M, r, c, d, ans;
int board[50][50];
int dx[4] = {-1, 0, 1, 0}; // 북, 동, 남, 서
int dy[4] = {0, 1, 0, -1};
void run() {
while (board[r][c] != WALL) {
if (board[r][c] == GO) ++ans;
board[r][c] = VISIT;
// 현재 바라보고 있는 방향 기준으로 90도씩 반시계 방향으로 돌려 봄
bool flag = 0;
for (int i = 0; i < 4; ++i) {
d = (d + 3) % 4; // 반시계 방향
int nr = r + dx[d], nc = c + dy[d];
if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
if (board[nr][nc] == GO) {
flag = 1;
r = nr, c = nc;
break;
}
}
if (flag) continue;
// 못 들어갔다면 방향 그대로 두고 후진
r -= dx[d], c -= dy[d];
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M >> r >> c >> d;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) cin >> board[i][j];
}
run();
cout << ans;
}풀고 나니 쉬운 문제. 반시계 방향은 (d + 3) % 4
후진은 x -= dx[d], y -= dy[d]
처음에 방을 로봇 청소기가 움직인다길래 자연스럽게 bfs 틀로 코드를 작성했는데 이 문제는 그냥 문제에 있는 절차 그대로를 코드로 옮겨주면 되는 거였다. bfs가 아니었음.
3190 | 뱀
#include <bits/stdc++.h>
using namespace std;
#define APPLE 1
#define SNAKE -1
deque<pair<int, int>> dq;
int N, K, L, d, t;
int board[101][101];
int dx[4] = {0, 1, 0, -1}; // 동, 북, 서, 남
int dy[4] = {1, 0, -1, 0};
bool OOB(int x, int y) {
return x < 1 || x > N || y < 1 || y > N;
}
void move() {
++t;
auto [head_x, head_y] = dq.front();
int nx = head_x + dx[d], ny = head_y + dy[d];
if (OOB(nx, ny) || board[nx][ny] == SNAKE) {
cout << t;
exit(0);
}
if (board[nx][ny] != APPLE) {
auto [tail_x, tail_y] = dq.back();
dq.pop_back();
board[tail_x][tail_y] = 0;
}
dq.push_front({nx, ny});
board[nx][ny] = SNAKE;
}
void run() {
dq.push_front({1, 1});
board[1][1] = SNAKE;
cin >> L;
for (int i = 0; i < L; ++i) {
int X;
char C;
cin >> X >> C;
while (t < X) move();
if (C == 'L') d = (d + 3) % 4;
else d = (d + 1) % 4;
}
while (1) move();
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> K;
for (int i = 0; i < K; ++i) {
int r, c;
cin >> r >> c;
board[r][c] = APPLE;
}
run();
}이제 deque이나 queue 등 STL 컨테이너 활용을 쉽게 떠올릴 수 있는 것 같다.
장족의 발전!
그리고 (1, 1)이 시작점인 걸 보고 이번 문제에선 범위를 처음부터 잘 적용해줬다! 👏
주의
처음에는
for (int i = 0; i < L; ++i) {
int X;
char C;
cin >> X >> C;
while (t < X) move();
if (C == 'L') d = (d + 3) % 4;
else d = (d + 1) % 4;
}이렇게 move()를 방향 전환 명령이 주어졌을 때만 실행했었다.
그런데 이렇게 작성하면, 마지막 명령 이후에도 뱀이 계속 움직여야 하는 경우를 놓치게 된다.
실제로는 방향 전환이 끝난 뒤에도 뱀이 벽에 부딪히거나 자기 몸에 닿을 때까지 계속 움직여야 하기 때문에,
입력을 모두 처리한 후에도 while (1) move(); 구문이 필요하다.
디버깅하면서 print를 찍어보고 문제를 파악하긴 했지만
처음 코드를 짤 때부터 이 흐름이 잘못되었음을 인지했어야 했다.
연습 많이 하자!
14500 | 테트로미노
ㅜ 모양 고려 안 된 오답 버전
#include <bits/stdc++.h>
using namespace std;
int dir[3];
int board[500][500];
bool vis[500][500];
int N, M, x, y, ans;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
void print() {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) cout << board[i][j] << ' ';
cout << '\n';
}
cout << '\n';
}
void update() {
bool vis[500][500] = {};
int summ = board[x][y];
int nx = x, ny = y;
vis[nx][ny] = 1;
for (int i = 0; i < 3; ++i) {
nx = nx + dx[dir[i]], ny = ny + dy[dir[i]];
vis[nx][ny] = 1;
if (nx < 0 || nx >= N || ny < 0 || ny >= M) return;
summ += board[nx][ny];
}
ans = max(ans, summ);
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) cout << vis[i][j] << ' ';
cout << '\n';
}
cout << '\n';
}
void dfs(int k) {
if (k == 3) {
update();
return;
}
for (int i = 0; i < 4; ++i) {
if (k > 0 && i == (dir[k - 1] + 2) % 4) continue;
dir[k] = i;
dfs(k + 1);
}
}
void run() {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
x = i;
y = j;
dfs(0);
}
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) cin >> board[i][j];
}
run();
cout << ans;
}출력해보고 이상한 점 깨달았다...
처음엔 인접한 칸들을 타고 타고 들어가게 했었는데
그러면 'ㅜ' 모양(또는 ㅏ, ㅓ, ㅗ 등)이 고려가 안 된다.
이 방식은 단순히 4칸을 연속해서 이어가는 구조이기 때문에
가운데에서 세 방향으로 뻗는 ‘ㅜ’ 형태는 만들 수가 없었다.
그것도 그렇고 dir[3]을 채워서 하는 게 비효율적이었다.
애초에 그냥 vis 배열을 두고 모양을 채워가는 것이 나았음.
바킹독님 풀이 참고 정답 버전
#include <bits/stdc++.h>
using namespace std;
int board[500][500];
bool vis[500][500];
int N, M, summ, ans;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
void dfs(int cx, int cy, int k) {
if (k == 4) {
ans = max(ans, summ);
return;
}
for (int d = 0; d < 4; ++d) {
int nx = cx + dx[d], ny = cy + dy[d];
if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
if (vis[nx][ny]) continue;
vis[nx][ny] = 1;
summ += board[nx][ny];
dfs(nx, ny, k + 1);
if (k == 2) {
dfs(cx, cy, k + 1);
}
vis[nx][ny] = 0;
summ -= board[nx][ny];
}
}
void run() {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
vis[i][j] = 1;
summ += board[i][j];
dfs(i, j, 1);
vis[i][j] = 0;
summ -= board[i][j];
}
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) cin >> board[i][j];
}
run();
cout << ans;
}와 진짜 이렇게 해야하는구나...
이 문제는 정답코드, 별해1, 별해2가 있었는데
정답코드는 러프하게 모든 조합 + bfs로 인접한지 확인 + 인접하다면 정답 업데이트였다.
그리고 별해1은 가능한 테트로미노 조합을 배열에 하드코딩값으로 넣고 돌리는 거였다.
그리고 마지막! dfs로 하되 칸 세 개가 채워지고 나서(k == 2), 현재 위치(cx, cy)에서 다시 한 번 dfs(cx, cy, k+1)를 해주는 것이다.
그럼 ㅏ, ㅗ, ㅜ, ㅓ를 처리해줄 수 있다.
이제껏 dfs 문제에서 한 방향으로 타고타고 들어가는 것만 생각해왔어서 저렇게 특정 조건에선 틀어서 dfs를 들어가 문제를 푸는 건 생각도 못했다.. 갈 길이 멀다
그리고 러프한 버전은 저번에 다솜파 문제에서 조합 구하고 + 인접한지 확인하는 유형을 풀었었는데도 아이디어를 떠올리지 못했다.
조합 + 인접한지 확인 = dfs + bfs 유형 새겨두기
13460 | 구슬 탈출 2
ver1. dfs 백트래킹
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define RED 1
#define BLUE 2
int N, M, ans = INT_MAX;
char board[10][10], board2[10][10];
pair<int, int> red, blue, red2, blue2;
bool is_red_fall, is_blue_fall;
int tilt_d[10];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
int who_first(int dir) {
if (dir == 0) {
if (red2.X > blue2.X) return RED;
return BLUE;
} else if (dir == 1) {
if (red2.Y < blue2.Y) return RED;
return BLUE;
} else if (dir == 2) {
if (red2.X < blue2.X) return RED;
return BLUE;
} else if (dir == 3) {
if (red2.Y > blue2.Y) return RED;
return BLUE;
}
return -1;
}
void roll(int &x, int &y, int dir, bool &is_fall) {
char ball = board2[x][y];
board2[x][y] = '.';
while (1) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (board2[nx][ny] != '.') {
if (board2[nx][ny] == 'O') is_fall = true;
break;
}
x = nx;
y = ny;
}
if (!is_fall) board2[x][y] = ball;
}
void tilt(int dir) {
int who = who_first(dir);
if (who == RED) {
roll(red2.X, red2.Y, dir, is_red_fall);
roll(blue2.X, blue2.Y, dir, is_blue_fall);
} else {
roll(blue2.X, blue2.Y, dir, is_blue_fall);
roll(red2.X, red2.Y, dir, is_red_fall);
}
}
void init() {
memcpy(board2, board, sizeof board);
red2 = red;
blue2 = blue;
is_red_fall = is_blue_fall = false;
}
void dfs(int k) {
if (k == 10) {
init();
for (int i = 0; i < 10; ++i) {
tilt(tilt_d[i]);
if (is_blue_fall) return;
if (is_red_fall) {
ans = min(ans, i);
return;
}
}
return;
}
for (int d = 0; d < 4; ++d) {
if (k > 0 && tilt_d[k - 1] == d) continue;
tilt_d[k] = d;
dfs(k + 1);
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
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') red = {i, j};
else if (board[i][j] == 'B') blue = {i, j};
}
}
dfs(0);
if (ans == INT_MAX) cout << -1;
else cout << ans;
}
/*
. 빈 칸
# 벽
O 구멍
R 빨간 구슬
B 파란 구슬
*/처음엔 dfs로 문제를 풀었었다. 기울이는 방향을 dfs로 정하고 시뮬레이션을 돌리는 것이다.
그런데 바킹독님 풀이를 보니 bfs로도 가능한 것이었다.
ver2. bfs
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int N, M, ans = -1;
char board[10][10];
int dist[10][10][10][10];
pair<int, int> red, blue;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
void bfs() {
queue<tuple<int, int, int, int>> q;
q.push({red.X, red.Y, blue.X, blue.Y});
dist[red.X][red.Y][blue.X][blue.Y] = 1;
while (!q.empty()) {
auto [rx, ry, bx, by] = q.front(); q.pop();
int cnt = dist[rx][ry][bx][by];
if (cnt > 10) return;
for (int d = 0; d < 4; ++d) {
int nrx = rx, nry = ry, nbx = bx, nby = by;
int move_r = 0, move_b = 0;
// blue 먼저
while (board[nbx + dx[d]][nby + dy[d]] == '.') {
nbx += dx[d];
nby += dy[d];
++move_b;
}
if (board[nbx + dx[d]][nby + dy[d]] == 'O') continue;
// red
while (board[nrx + dx[d]][nry + dy[d]] == '.') {
nrx += dx[d];
nry += dy[d];
++move_r;
}
if (board[nrx + dx[d]][nry + dy[d]] == 'O') {
ans = cnt;
return;
}
// 둘이 겹쳤다면 늦게 출발한(더 많이 움직인) 구슬을 한 칸 뒤로 이동
if (nrx == nbx && nry == nby) {
if (move_r > move_b) {
nrx -= dx[d];
nry -= dy[d];
} else {
nbx -= dx[d];
nby -= dy[d];
}
}
if (dist[nrx][nry][nbx][nby]) continue;
q.push({nrx, nry, nbx, nby});
dist[nrx][nry][nbx][nby] = cnt + 1;
}
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
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') {
red = {i, j};
board[i][j] = '.';
}
else if (board[i][j] == 'B') {
blue = {i, j};
board[i][j] = '.';
}
}
}
bfs();
cout << ans;
}이 문제는 빨간 구슬이 구멍에 도달하기까지의 최단 거리를 묻는 문제다.
각 상태는 (빨간 구슬 위치, 파란 구슬 위치)로 표현될 수 있고,
하나의 기울이기(→ 이동)는 간선 역할을 한다.
기울인 이후의 상태는 명확하게 결정되므로, 각 상태는 고정된 다음 상태를 가진다.
그렇기 때문에 BFS로 풀 수 있는 문제였다.
// dist[red_x][red_y][blue_x][blue_y]에 도달한 최소 횟수를 저장
int dist[10][10][10][10];dist 배열은 4차원으로 만들어야 한다. (redX, redY), (blueX, blueY)의 모든 조합을 담아야하기 때문이다.
또, 문제의 제약 조건인 최대 10회 이내 기울이기를 활용하여,
dist 값이 10을 초과한 경우에는 더 이상 탐색하지 않고 return한다.
