[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 :16234] 인구 이동
K
Koa
문제 번호
16234
문제 요구 사항
입력
N x N의 땅이 주어진다.
각 칸에 몇 명이 사는지 주어진다.
인구 이동이 일어나는 조건 L, R이 주어진다.
출력
인접한 두 칸의 인구 차이가 L이상 R 이하인 경우, 인구 이동이 일어난다.
인구 이동이 며칠 동안 발생하는지 구해서 출력한다.
해설
문제 상에서 인구 이동을 하는 과정은 DFS든지, BFS든지 일단 구현할 수 있다.
단, 인구 이동이 잘 끝나는지 검사 해야 한다. 왜일까.
일단 인구이동의 조건 중, L이 0이상이다. 그 말은 모든 칸이 같은 인구 수가 되었어도 인구 이동이 일어난 것으로 생각할 수 있다. 따라서, 이 조건을 고려하여 정말 인구 이동이 일어난 건지 확인해야 한다.
코드
/*
[16234: 인구 이동](https://www.acmicpc.net/problem/16234)
Tier: Gold 4
Category: bfs, graphs, graph_traversal, implementation, simulation
*/
#include <bits/stdc++.h>
using namespace std;
#define for1(s, e) for(int i = s; i < e; i++)
#define for1j(s, e) for(int j = s; j < e; j++)
#define forEach(k) for(auto i : k)
#define forEachj(k) for(auto j : k)
#define sz(vct) vct.size()
#define all(vct) vct.begin(), vct.end()
#define sortv(vct) sort(vct.begin(), vct.end())
#define uniq(vct) sort(all(vct));vct.erase(unique(all(vct)), vct.end())
#define fi first
#define se second
#define INF (1ll << 60ll)
typedef unsigned long long ull;
typedef long long ll;
typedef ll llint;
typedef unsigned int uint;
typedef unsigned long long int ull;
typedef ull ullint;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef pair<double, int> pdi;
typedef pair<string, string> pss;
typedef vector<int> iv1;
typedef vector<iv1> iv2;
typedef vector<ll> llv1;
typedef vector<llv1> llv2;
typedef vector<pii> piiv1;
typedef vector<piiv1> piiv2;
typedef vector<pll> pllv1;
typedef vector<pllv1> pllv2;
typedef vector<pdd> pddv1;
typedef vector<pddv1> pddv2;
const double EPS = 1e-8;
const double PI = acos(-1);
template<typename T>
T sq(T x) { return x * x; }
int sign(ll x) { return x < 0 ? -1 : x > 0 ? 1 : 0; }
int sign(int x) { return x < 0 ? -1 : x > 0 ? 1 : 0; }
int sign(double x) { return abs(x) < EPS ? 0 : x < 0 ? -1 : 1; }
int N, L, R, ans;
iv2 ar;
int dy[] = { 0, 0, 1, -1 };
int dx[] = { 1, -1, 0, 0 };
void solve() {
cin >> N >> L >> R;
ar.resize(N, iv1(N, 0));
vector< vector<bool>> chk(N, vector<bool>(N, false));
for1(0, N) {
for1j(0, N) {
cin >> ar[i][j];
}
}
while(1) {
int move_cnt = 0;
for1(0, N) {
for1j(0, N) {
chk[i][j] = false;
}
}
for1(0, N) {
for1j(0, N) {
if(!chk[i][j]) {
queue <pii> Q;
vector <pii> Q2;
Q.push({i, j});
Q2.push_back({i, j});
chk[i][j] = true;
while(!Q.empty()) {
pii here = Q.front();
Q.pop();
for(int d = 0; d < 4; d++) {
int ny = here.first + dy[d];
int nx = here.second + dx[d];
if(ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
if(chk[ny][nx]) continue;
int diff = abs(ar[here.first][here.second] - ar[ny][nx]);
if(diff < L || diff > R) continue;
Q.push({ ny, nx });
Q2.push_back({ ny, nx });
chk[ny][nx] = true;
}
}
if(Q2.size() > 1) {
int sm = 0;
bool flag = true;
for(pii axis : Q2) {
sm += ar[axis.first][axis.second];
flag = flag && (ar[Q2[0].first][Q2[0].second] == ar[axis.first][axis.second]);
}
if(!flag) move_cnt++;
int val = sm / Q2.size();
for(pii axis : Q2) {
ar[axis.first][axis.second] = val;
}
}
}
}
}
if(move_cnt == 0) break;
ans++;
}
cout << ans;
}
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 : 16948] 데스 나이트
문제 요구 사항 N x N 크기의 체스판에서, (r1, c1) → (r2 → c2) 로의 최소 이동 횟수를 출력한다. 해설 문제에서 주어지는 방향에 따라 BFS를 잘 구현하자. 일반적인 나이트의 움직임이 아니다. 코드
[BOJ :4779] 칸토어 집합
문제 요구 사항 N번째 칸토어 집합의 근사를 출력한다. 해설 일단, N번째 칸토어 집합을 DP[n]이라 하자. 이때 아래의 식이 성립한다. 최대 N은 12이기 때문에 최대 문자열의 길이는 3^12 = 531,441이다. 따라서, 직접 문자열을 저장만 잘 반복없이 한다면 충분히 다 담아낼 수 있다. 코드
[BOJ : 2146] 다리 만들기
N x N 크기의 지도가 주어진다. 0은 바다, 1은 육지를 나타낸다. 출력 한 대륙에서 다른 대륙으로 다리를 놓았을 때, 가장 짧은 다리의 길이를 출력한다. 해설 처음에 생각을 잘못 접근하면 이상한 길로 샐 수 있는 문제다. 단순하게 각 대륙에서 무수히 많은 사람이 동시에서 출발하고, 어딘가에서 만나걸라고 생각한다. 그리고 만난 사람들에 대해서, 지금까지 온 거리를 확인해보자. 말이 어려울 수 있다.. 코드로 보자. 코드