백준 문제 풀이

일단 풀고 기록 남기는 곳

[BOJ : 16948] 데스 나이트

문제 요구 사항 N x N 크기의 체스판에서, (r1, c1) → (r2 → c2) 로의 최소 이동 횟수를 출력한다. 해설 문제에서 주어지는 방향에 따라 BFS를 잘 구현하자. 일반적인 나이트의 움직임이 아니다. 코드

Koa

2024/07/29 10:31 PM

[BOJ :4779] 칸토어 집합

문제 요구 사항 N번째 칸토어 집합의 근사를 출력한다. 해설 일단, N번째 칸토어 집합을 DP[n]이라 하자. 이때 아래의 식이 성립한다. 최대 N은 12이기 때문에 최대 문자열의 길이는 3^12 = 531,441이다. 따라서, 직접 문자열을 저장만 잘 반복없이 한다면 충분히 다 담아낼 수 있다. 코드

Koa

2024/07/29 10:22 PM

[BOJ : 2146] 다리 만들기

N x N 크기의 지도가 주어진다. 0은 바다, 1은 육지를 나타낸다. 출력 한 대륙에서 다른 대륙으로 다리를 놓았을 때, 가장 짧은 다리의 길이를 출력한다. 해설 처음에 생각을 잘못 접근하면 이상한 길로 샐 수 있는 문제다. 단순하게 각 대륙에서 무수히 많은 사람이 동시에서 출발하고, 어딘가에서 만나걸라고 생각한다. 그리고 만난 사람들에 대해서, 지금까지 온 거리를 확인해보자. 말이 어려울 수 있다.. 코드로 보자. 코드

Koa

2024/07/25 8:51 PM

[BOJ :16234] 인구 이동

문제 요구 사항 입력 N x N의 땅이 주어진다. 각 칸에 몇 명이 사는지 주어진다. 인구 이동이 일어나는 조건 L, R이 주어진다. 출력 인접한 두 칸의 인구 차이가 L이상 R 이하인 경우, 인구 이동이 일어난다. 인구 이동이 며칠 동안 발생하는지 구해서 출력한다. 해설 문제 상에서 인구 이동을 하는 과정은 DFS든지, BFS든지 일단 구현할 수 있다. 단, 인구 이동이 잘 끝나는지 검사 해야 한다. 왜일까. 일단 인구이동의 조건 중, L이 0이상이다. 그 말은 모든 칸이 같은 인구 수가 되었어도 인구 이동이 일어난 것으로 생각할 수 있다. 따라서, 이 조건을 고려하여 정말 인구 이동이 일어난 건지 확인해야 한다. 코드

Koa

2024/07/24 10:34 PM

16234

koa

백준 문제 풀이

[BOJ : 2146] 다리 만들기

Koa

Jul 25, 20245m

N x N 크기의 지도가 주어진다.

0은 바다, 1은 육지를 나타낸다.

출력

한 대륙에서 다른 대륙으로 다리를 놓았을 때, 가장 짧은 다리의 길이를 출력한다.

해설

처음에 생각을 잘못 접근하면 이상한 길로 샐 수 있는 문제다.

단순하게 각 대륙에서 무수히 많은 사람이 동시에서 출발하고, 어딘가에서 만나걸라고 생각한다.

그리고 만난 사람들에 대해서, 지금까지 온 거리를 확인해보자.

말이 어려울 수 있다.. 코드로 보자.

코드

/*
[2146: 다리 만들기](https://www.acmicpc.net/problem/2146)

Tier: Gold 3 
Category: bfs, graphs, graph_traversal
*/


#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; }

ll N;
llv2 board, dist;
ll dy[] = { 0, 0, 1, -1 };
ll dx[] = { 1, -1, 0, 0 };
// 방향 배열이다. BFS 탐색 시에 요런거 선언하자.
// "2110"[d] - "1"  
// "1201"[d] - "1" 
// 요런식도 가능하다.

void solve() {
  cin >> N;
  board.resize(N, llv1(N));  // 문제에서 주어진 지도
  dist.resize(N, llv1(N, INF)); // 거리를 저장할 거다.

  queue <pll> Q; // BFS를 할거니 큐를 선언한다. (y, x) 좌표를 담는다.

  for1(0, N) {
    for1j(0, N) {
      cin >> board[i][j];
    }
  }

  vector<vector<bool>> chk(N, vector<bool>(N, false)); 

  ll area_num = 2;
  for1(0, N) {
    for1j(0, N) {
      if(board[i][j] && !chk[i][j]) {
        Q.push({ i, j });
        chk[i][j] = true;

        while(!Q.empty()) {
          auto [y, x] = Q.front(); Q.pop();
          board[y][x] = area_num;

          for(int d = 0; d < 4; d++) {
            ll ny = y + dy[d];
            ll nx = x + dx[d];

            if(ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
            if(chk[ny][nx]) continue;
            if(board[ny][nx] == 0) continue;
            
            chk[ny][nx] = true;
            Q.push({ny, nx});
          }
        }

        area_num++;
      }
    }
  }

  // 각 대륙에 대한 정보로 board 정보를 바꾸어 남겼다.
  // 하지만 여전히 바다는 0이다.
  

  chk = vector<vector<bool>>(N, vector<bool>(N, false));


  for1(0, N) {
    for1j(0, N) {
      if(board[i][j] != 0) {
        Q.push({ i, j });
        chk[i][j] = true;
        dist[i][j] = 0;

        // 모든 대륙에서 동시에 출발시키기 위해, 한번에 큐에 넣고, 거리를 0으로 저장한다.
      }
    }
  }

  // 이제 BFS를 다시 수행한다.
  while(!Q.empty()) {
    auto [y, x] = Q.front(); Q.pop();

    for(int d = 0; d < 4; d++) {
      ll ny = y + dy[d];
      ll nx = x + dx[d];

      if(ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
      if(chk[ny][nx]) continue;
      if(board[ny][nx] >= 2) continue; // 다음 이동할 곳이 대륙이라면 (혹은 누군가 왔다면) 넘어간다.
      board[ny][nx] = board[y][x];
      dist[ny][nx] = dist[y][x] + 1;  // 무조건 미방문된 곳에 왔을테니 바로 거리를 기록한다.
      
      chk[ny][nx] = true;
      Q.push({ny, nx});
    }
  }

  ll ans = INF;

  for1(0, N) {
    for1j(0, N) {
      // 인접한 곳이 서로 다른 board 값을 가지고 있다면 만난 곳이다.
      if(i + 1 < N) {
        if(board[i][j] != board[i+1][j]) ans = min(ans, dist[i][j] + dist[i+1][j]);
      }
      if(j + 1 < N) {
        if(board[i][j] != board[i][j+1]) ans = min(ans, dist[i][j] + dist[i][j+1]);
      }
    }
  }

  cout << ans;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(NULL);cout.tie(NULL);
  int tc = 1; // cin >> tc;
  while(tc--) solve();
  
}

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'!