-
[λ°±μ€(BOJ) 7576λ²] ν λ§ν (C++)PS(Problem Solving)/C++ 2022. 1. 23. 23:35λ°μν
λ¬Έμ λ§ν¬
https://www.acmicpc.net/problem/7576
λ¬Έμ μ 보
μ λ ₯
첫 μ€μλ μμμ ν¬κΈ°λ₯Ό λνλ΄λ λ μ μ M,Nμ΄ μ£Όμ΄μ§λ€. Mμ μμμ κ°λ‘ μΉΈμ μ, Nμ μμμ μΈλ‘ μΉΈμ μλ₯Ό λνλΈλ€. λ¨, 2 ≤ M,N ≤ 1,000 μ΄λ€. λμ§Έ μ€λΆν°λ νλμ μμμ μ μ₯λ ν λ§ν λ€μ μ λ³΄κ° μ£Όμ΄μ§λ€. μ¦, λμ§Έ μ€λΆν° Nκ°μ μ€μλ μμμ λ΄κΈ΄ ν λ§ν μ μ λ³΄κ° μ£Όμ΄μ§λ€. νλμ μ€μλ μμ κ°λ‘μ€μ λ€μ΄μλ ν λ§ν μ μνκ° Mκ°μ μ μλ‘ μ£Όμ΄μ§λ€. μ μ 1μ μ΅μ ν λ§ν , μ μ 0μ μ΅μ§ μμ ν λ§ν , μ μ -1μ ν λ§ν κ° λ€μ΄μμ§ μμ μΉΈμ λνλΈλ€.
ν λ§ν κ° νλ μ΄μ μλ κ²½μ°λ§ μ λ ₯μΌλ‘ μ£Όμ΄μ§λ€.
μΆλ ₯
μ¬λ¬λΆμ ν λ§ν κ° λͺ¨λ μ΅μ λκΉμ§μ μ΅μ λ μ§λ₯Ό μΆλ ₯ν΄μΌ νλ€. λ§μ½, μ μ₯λ λλΆν° λͺ¨λ ν λ§ν κ° μ΅μ΄μλ μνμ΄λ©΄ 0μ μΆλ ₯ν΄μΌ νκ³ , ν λ§ν κ° λͺ¨λ μ΅μ§λ λͺ»νλ μν©μ΄λ©΄ -1μ μΆλ ₯ν΄μΌ νλ€.
νμ΄
μ΄ λ¬Έμ λ BFSμ μμ© λ¬Έμ λ‘ μμμ μ΄ μ¬λ¬ κ°μΌ λ λ¬Έμ λ₯Ό ν΄κ²°νλ λ°©λ²μ΄λ€. μμμ μ λͺ¨λ νμ λ£μ΄λ²λ¦¬κ³ BFSλ₯Ό λλ €μ ν΄κ²°νλ€!
μμ€ μ½λ
#include <bits/stdc++.h> using namespace std; #define X first #define Y second int board[1002][1002]; int dist[1002][1002]; // μ΅μ λ μ§ μ μ₯ν λ°°μ΄ int n, m; int dx[4] = { 1, 0, -1, 0 }; int dy[4] = { 0, 1, 0, -1 }; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> m >> n; queue<pair<int, int>> Q; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> board[i][j]; if (board[i][j] == 1) { Q.push({i, j}); // μ΅μ ν λ§ν (μμ μ’ν)λ₯Ό νμ λ£μ΄λ²λ¦°λ€. } if (board[i][j] == 0) { dist[i][j] = -1; // μ΅μ§ μμ ν λ§ν μ μ΅μ λ μ§λ₯Ό -1λ‘ μ μ₯νλ€. (μ΅μ ν λ§ν μ ν λ§ν κ° μλ μΉΈμ 0μΌλ‘ μ΄κΈ°ν λμ΄ μμ!) } } } while (!Q.empty()) { auto cur = Q.front(); Q.pop(); for (int dir = 0; dir < 4; dir++) { int nx = cur.X + dx[dir]; int ny = cur.Y + dy[dir]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) { continue; } if (dist[nx][ny] >= 0) { continue; // μ΅μ ν λ§ν , ν λ§ν κ° μλ μΉΈ } dist[nx][ny] = dist[cur.X][cur.Y] + 1; Q.push({nx, ny}); } } int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (dist[i][j] == -1) { cout << "-1"; return 0; } ans = max(ans, dist[i][j]); } } cout << ans; return 0; }
λ°μν