[BOJ : 16948] 데스 나이트
문제 요구 사항 N x N 크기의 체스판에서, (r1, c1) → (r2 → c2) 로의 최소 이동 횟수를 출력한다. 해설 문제에서 주어지는 방향에 따라 BFS를 잘 구현하자. 일반적인 나이트의 움직임이 아니다. 코드
- KoaK
백준 문제 풀이
[BOJ :4779] 칸토어 집합
문제 요구 사항 N번째 칸토어 집합의 근사를 출력한다. 해설 일단, N번째 칸토어 집합을 DP[n]이라 하자. 이때 아래의 식이 성립한다. 최대 N은 12이기 때문에 최대 문자열의 길이는 3^12 = 531,441이다. 따라서, 직접 문자열을 저장만 잘 반복없이 한다면 충분히 다 담아낼 수 있다. 코드
- KoaK
[BOJ : 2146] 다리 만들기
N x N 크기의 지도가 주어진다. 0은 바다, 1은 육지를 나타낸다. 출력 한 대륙에서 다른 대륙으로 다리를 놓았을 때, 가장 짧은 다리의 길이를 출력한다. 해설 처음에 생각을 잘못 접근하면 이상한 길로 샐 수 있는 문제다. 단순하게 각 대륙에서 무수히 많은 사람이 동시에서 출발하고, 어딘가에서 만나걸라고 생각한다. 그리고 만난 사람들에 대해서, 지금까지 온 거리를 확인해보자. 말이 어려울 수 있다.. 코드로 보자. 코드
- KoaK
[BOJ :16234] 인구 이동
문제 요구 사항 입력 N x N의 땅이 주어진다. 각 칸에 몇 명이 사는지 주어진다. 인구 이동이 일어나는 조건 L, R이 주어진다. 출력 인접한 두 칸의 인구 차이가 L이상 R 이하인 경우, 인구 이동이 일어난다. 인구 이동이 며칠 동안 발생하는지 구해서 출력한다. 해설 문제 상에서 인구 이동을 하는 과정은 DFS든지, BFS든지 일단 구현할 수 있다. 단, 인구 이동이 잘 끝나는지 검사 해야 한다. 왜일까. 일단 인구이동의 조건 중, L이 0이상이다. 그 말은 모든 칸이 같은 인구 수가 되었어도 인구 이동이 일어난 것으로 생각할 수 있다. 따라서, 이 조건을 고려하여 정말 인구 이동이 일어난 건지 확인해야 한다. 코드
- KoaK
16234
Ko
koa백준 문제 풀이
[BOJ : 16948] 데스 나이트
K
Koa
문제 요구 사항
N x N 크기의 체스판에서, (r1, c1) → (r2 → c2) 로의 최소 이동 횟수를 출력한다.
해설
문제에서 주어지는 방향에 따라 BFS를 잘 구현하자. 일반적인 나이트의 움직임이 아니다.
코드
/*
[16948: 데스 나이트](https://www.acmicpc.net/problem/16948)
Tier: Silver 1
Category: bfs, graphs, graph_traversal
*/
#include <bits/stdc++.h>
using namespace std;
#define for1(s, e) for(int i = s; i < e; i++)
#define fi first
#define se second
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> llv1;
typedef vector<llv1> llv2;
ll N, r1, c1, r2, c2;
llv2 dist;
vector< vector <bool>> visited;
void solve() {
cin >> N;
cin >> r1 >> c1 >> r2 >> c2;
dist.resize(N + 1, llv1(N + 1, -1));
visited.resize(N + 1, vector<bool>(N + 1, false));
queue<pll> q;
q.push({r1, c1});
dist[r1][c1] = 0;
visited[r1][c1] = true;
while(!q.empty()) {
auto [r, c] = q.front();
q.pop();
if(r == r2 && c == c2) {
cout << dist[r][c] << endl; // 도착지점에 도달한 경우, 바로 최단거리 출력 후 종료
return;
}
for1(0, 6) {
int nr = r + "002244"[i] - '2'; // 데스나이트의 이동 가능한 방향 6가지
int nc = c + "130413"[i] - '2';
if(nr < 0 || nr >= N || nc < 0 || nc >= N) continue; // 1. 0 <= nr, nc < N
if(visited[nr][nc]) continue; // 2. 방문된 경우 제외(중복해서 방문되었다는 것은 최단거리가 아님)
visited[nr][nc] = true;
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});
}
}
cout << -1 << endl; // 도착할 수 없는 경우 -1 출력
}
int main() {
ios::sync_with_stdio(0);
cin.tie(NULL);cout.tie(NULL);
int tc = 1; // cin >> tc;
while(tc--) solve();
}Ko
Subscribe to 'koa'
Subscribe to my site to be the first to receive notifications and emails about the latest updates, including new posts.
Join SlashPage and subscribe to 'koa'!
Join SlashPage and subscribe to 'koa'!
Subscribe
Other posts in '백준 문제 풀이'
[BOJ :4779] 칸토어 집합
문제 요구 사항 N번째 칸토어 집합의 근사를 출력한다. 해설 일단, N번째 칸토어 집합을 DP[n]이라 하자. 이때 아래의 식이 성립한다. 최대 N은 12이기 때문에 최대 문자열의 길이는 3^12 = 531,441이다. 따라서, 직접 문자열을 저장만 잘 반복없이 한다면 충분히 다 담아낼 수 있다. 코드
[BOJ : 2146] 다리 만들기
N x N 크기의 지도가 주어진다. 0은 바다, 1은 육지를 나타낸다. 출력 한 대륙에서 다른 대륙으로 다리를 놓았을 때, 가장 짧은 다리의 길이를 출력한다. 해설 처음에 생각을 잘못 접근하면 이상한 길로 샐 수 있는 문제다. 단순하게 각 대륙에서 무수히 많은 사람이 동시에서 출발하고, 어딘가에서 만나걸라고 생각한다. 그리고 만난 사람들에 대해서, 지금까지 온 거리를 확인해보자. 말이 어려울 수 있다.. 코드로 보자. 코드
[BOJ :16234] 인구 이동
문제 요구 사항 입력 N x N의 땅이 주어진다. 각 칸에 몇 명이 사는지 주어진다. 인구 이동이 일어나는 조건 L, R이 주어진다. 출력 인접한 두 칸의 인구 차이가 L이상 R 이하인 경우, 인구 이동이 일어난다. 인구 이동이 며칠 동안 발생하는지 구해서 출력한다. 해설 문제 상에서 인구 이동을 하는 과정은 DFS든지, BFS든지 일단 구현할 수 있다. 단, 인구 이동이 잘 끝나는지 검사 해야 한다. 왜일까. 일단 인구이동의 조건 중, L이 0이상이다. 그 말은 모든 칸이 같은 인구 수가 되었어도 인구 이동이 일어난 것으로 생각할 수 있다. 따라서, 이 조건을 고려하여 정말 인구 이동이 일어난 건지 확인해야 한다. 코드