-
[๋ฐฑ์ค(BOJ) 4179๋ฒ] ๋ถ! (C++)PS(Problem Solving)/C++ 2022. 1. 30. 14:23๋ฐ์ํ
๋ฌธ์ ๋งํฌ
https://www.acmicpc.net/problem/4179
๋ฌธ์ ์ ๋ณด
์ ๋ ฅ
์ ๋ ฅ์ ์ฒซ์งธ ์ค์๋ ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถ๋ ๋ ์ ์ R๊ณผ C๊ฐ ์ฃผ์ด์ง๋ค. ๋จ, 1 ≤ R, C ≤ 1000 ์ด๋ค. R์ ๋ฏธ๋ก ํ์ ๊ฐ์, C๋ ์ด์ ๊ฐ์์ด๋ค.
๋ค์ ์ ๋ ฅ์ผ๋ก R์ค๋์ ๊ฐ๊ฐ์ ๋ฏธ๋ก ํ์ด ์ฃผ์ด์ง๋ค.
๊ฐ๊ฐ์ ๋ฌธ์๋ค์ ๋ค์์ ๋ปํ๋ค.
- #: ๋ฒฝ
- .: ์ง๋๊ฐ ์ ์๋ ๊ณต๊ฐ
- J: ์งํ์ด์ ๋ฏธ๋ก์์์ ์ด๊ธฐ์์น (์ง๋๊ฐ ์ ์๋ ๊ณต๊ฐ)
- F: ๋ถ์ด ๋ ๊ณต๊ฐ
J๋ ์ ๋ ฅ์์ ํ๋๋ง ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
์งํ์ด๊ฐ ๋ถ์ด ๋๋ฌํ๊ธฐ ์ ์ ๋ฏธ๋ก๋ฅผ ํ์ถ ํ ์ ์๋ ๊ฒฝ์ฐ IMPOSSIBLE ์ ์ถ๋ ฅํ๋ค.
์งํ์ด๊ฐ ๋ฏธ๋ก๋ฅผ ํ์ถํ ์ ์๋ ๊ฒฝ์ฐ์๋ ๊ฐ์ฅ ๋น ๋ฅธ ํ์ถ์๊ฐ์ ์ถ๋ ฅํ๋ค.
ํ์ด
์ด ๋ฌธ์ ๋ BFS์ ์์ฉ ๋ฌธ์ ๋ก ์์์ ์ด ๋ ์ข ๋ฅ์ผ ๋ ํด๊ฒฐํ๋ ๋ฌธ์ ์ด๋ค. ์์์ ์ด ๋ ์ข ๋ฅ์ผ ๊ฒฝ์ฐ์ ๋ถ์ ๋ํ BFS์ ์งํ์ด์ ๋ํ BFS๋ฅผ ๋ ๋ค ๋๋ ค์ ํด๊ฒฐํ ์ ์๋ค.
์์ค ์ฝ๋
#include <bits/stdc++.h> using namespace std; #define X first #define Y second string board[1002]; int dist1[1002][1002]; // ๋ถ์ ์ ํ ์๊ฐ์ ์ ์ฅํ ๋ฐฐ์ด int dist2[1002][1002]; // ์งํ์ด์ ์ด๋ ์๊ฐ์ ์ ์ฅํ ๋ฐฐ์ด int r, c; 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 >> r >> c; for (int i = 0; i < r; i++) { fill(dist1[i], dist1[i] + c, -1); // ๋ฐฐ์ด์ ๋ฏธ๋ฆฌ -1๋ก ์ด๊ธฐํํด๋๋ฉด vis ๋ฐฐ์ด์ ๋ฐ๋ก ๋ฌ์ ๋ฐฉ๋ฌธ ์ฌ๋ถ๋ฅผ ํ์ธํ ํ์๊ฐ ์๋ค! fill(dist2[i], dist2[i] + c, -1); // ๋ฐฐ์ด์ ๋ฏธ๋ฆฌ -1๋ก ์ด๊ธฐํํด๋๋ฉด vis ๋ฐฐ์ด์ ๋ฐ๋ก ๋ฌ์ ๋ฐฉ๋ฌธ ์ฌ๋ถ๋ฅผ ํ์ธํ ํ์๊ฐ ์๋ค! } for (int i = 0; i < r; i++) { cin >> board[i]; } queue<pair<int, int>> Q1; // ๋ถ์ ๋ํ BFS queue<pair<int, int>> Q2; // ์งํ์ด์ ๋ํ BFS for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (board[i][j] == 'F') { // ๋ถ์ ์์ ์ขํ Q1.push({i, j}); dist1[i][j] = 0; } if (board[i][j] == 'J') { // ์งํ์ด์ ์์ ์ขํ Q2.push({i, j}); dist2[i][j] = 0; } } } // ๋ถ์ ๋ํ BFS while (!Q1.empty()) { auto cur = Q1.front(); Q1.pop(); for (int dir = 0; dir < 4; dir++) { int nx = cur.X + dx[dir]; int ny = cur.Y + dy[dir]; if (nx < 0 || nx >= r || ny < 0 || ny >= c) { continue; } if (dist1[nx][ny] >= 0 || board[nx][ny] == '#') { continue; } dist1[nx][ny] = dist1[cur.X][cur.Y] + 1; Q1.push({nx, ny}); } } // ์งํ์ด์ ๋ํ BFS while (!Q2.empty()) { auto cur = Q2.front(); Q2.pop(); for (int dir = 0; dir < 4; dir++) { int nx = cur.X + dx[dir]; int ny = cur.Y + dy[dir]; if (nx < 0 || nx >= r || ny < 0 || ny >= c) { // ๋ฒ์๋ฅผ ๋ฒ์ด๋ฌ๋ค๋ ๊ฒ์ ๋ฏธ๋ก๋ฅผ ํ์ถ ํ๋ค๋ ๊ฒ! cout << dist2[cur.X][cur.Y] + 1; return 0; } if (dist2[nx][ny] >= 0 || board[nx][ny] == '#') { continue; } // ๋ถ์ด ๋จผ์ ๋์ฐฉํ์ผ๋ฉด ์งํ์ด๋ ๋ชป์ง๋๊ฐ! if (dist1[nx][ny] != -1 && dist1[nx][ny] <= dist2[cur.X][cur.Y] + 1) { continue; } dist2[nx][ny] = dist2[cur.X][cur.Y] + 1; Q2.push({nx, ny}); } } cout << "IMPOSSIBLE"; return 0; }
๋ฐ์ํ