๐ฃ ๋ฌธ์ ์ดํด
๋ก๋ด ์ฒญ์๊ธฐ๊ฐ ์๋ ์ฅ์๋ N×M ํฌ๊ธฐ์ ์ง์ฌ๊ฐํ์ผ๋ก ๋ํ๋ผ ์ ์์ผ๋ฉฐ, 1×1ํฌ๊ธฐ์ ์ ์ฌ๊ฐํ ์นธ์ผ๋ก ๋๋์ด์ ธ ์๋ค. ๊ฐ๊ฐ์ ์นธ์ ๋ฒฝ ๋๋ ๋น ์นธ์ด๋ค. ์ฒญ์๊ธฐ๋ ๋ฐ๋ผ๋ณด๋ ๋ฐฉํฅ์ด ์์ผ๋ฉฐ, ์ด ๋ฐฉํฅ์ ๋, ์, ๋จ, ๋ถ์ค ํ๋์ด๋ค. ์ง๋์ ๊ฐ ์นธ์ (r, c)๋ก ๋ํ๋ผ ์ ์๊ณ , r์ ๋ถ์ชฝ์ผ๋ก๋ถํฐ ๋จ์ด์ง ์นธ์ ๊ฐ์, c๋ ์์ชฝ์ผ๋ก๋ถํฐ ๋จ์ด์ง ์นธ์ ๊ฐ์์ด๋ค.
๋ก๋ด ์ฒญ์๊ธฐ๋ ๋ค์๊ณผ ๊ฐ์ด ์๋ํ๋ค.
- ํ์ฌ ์์น๋ฅผ ์ฒญ์ํ๋ค.
- ํ์ฌ ์์น์์ ํ์ฌ ๋ฐฉํฅ์ ๊ธฐ์ค์ผ๋ก ์ผ์ชฝ๋ฐฉํฅ๋ถํฐ ์ฐจ๋ก๋๋ก ํ์์ ์งํํ๋ค.
- ์ผ์ชฝ ๋ฐฉํฅ์ ์์ง ์ฒญ์ํ์ง ์์ ๊ณต๊ฐ์ด ์กด์ฌํ๋ค๋ฉด, ๊ทธ ๋ฐฉํฅ์ผ๋ก ํ์ ํ ๋ค์ ํ ์นธ์ ์ ์งํ๊ณ 1๋ฒ๋ถํฐ ์งํํ๋ค.
- ์ผ์ชฝ ๋ฐฉํฅ์ ์ฒญ์ํ ๊ณต๊ฐ์ด ์๋ค๋ฉด, ๊ทธ ๋ฐฉํฅ์ผ๋ก ํ์ ํ๊ณ 2๋ฒ์ผ๋ก ๋์๊ฐ๋ค.
- ๋ค ๋ฐฉํฅ ๋ชจ๋ ์ฒญ์๊ฐ ์ด๋ฏธ ๋์ด์๊ฑฐ๋ ๋ฒฝ์ธ ๊ฒฝ์ฐ์๋, ๋ฐ๋ผ๋ณด๋ ๋ฐฉํฅ์ ์ ์งํ ์ฑ๋ก ํ ์นธ ํ์ง์ ํ๊ณ 2๋ฒ์ผ๋ก ๋์๊ฐ๋ค.
- ๋ค ๋ฐฉํฅ ๋ชจ๋ ์ฒญ์๊ฐ ์ด๋ฏธ ๋์ด์๊ฑฐ๋ ๋ฒฝ์ด๋ฉด์, ๋ค์ชฝ ๋ฐฉํฅ์ด ๋ฒฝ์ด๋ผ ํ์ง๋ ํ ์ ์๋ ๊ฒฝ์ฐ์๋ ์๋์ ๋ฉ์ถ๋ค.
๋ก๋ด ์ฒญ์๊ธฐ๋ ์ด๋ฏธ ์ฒญ์๋์ด์๋ ์นธ์ ๋ ์ฒญ์ํ์ง ์์ผ๋ฉฐ, ๋ฒฝ์ ํต๊ณผํ ์ ์๋ค.
๊ตฌํ ๋ฌธ์ ์ด๊ธฐ์ ๋ฌธ์ ์กฐ๊ฑด์ ์ ๊ตฌํํ๋ ๊ฒ์ ์ง์คํ๋ค.
๐ญ ํ์ด ๊ณผ์
ํ์ด๋ฅผ ์ข ์ฐพ์๋ดค๋๋ฐ, ์ฌ๊ท๋ฅผ ์ฌ์ฉํด์ BFS, DFS ๋ฐฉ์์ผ๋ก ํ์ด๋ธ ๋ถ๋ค๋ ๊ฝค ์์๋ค.
๊ทผ๋ฐ ๊ทธ๋ฅ ๋ฐ๋ณต๋ฌธ๊ณผ if๋ฌธ์ผ๋ก๋ ํ ์ ์์ ๊ฒ ๊ฐ๋ค๋ ์๊ฐ์ ๋ฌธ์ ์กฐ๊ฑด์ ๊ทธ๋๋ก ๊ตฌํํ๋ ๊ฒ์ ์ง์คํด๋ณด์๋ค.
1. ํ์ฌ ์์น๊ฐ ์ฒญ์๊ฐ ๊ฐ๋ฅํ๋ฐ ์๋์ด์๋ ๊ณณ(0)์ด๋ผ๋ฉด ์ฒญ์๋ฅผ ์ํํ๋ค.(2๋ก ๋ณ๊ฒฝ)
2. ์ฌ๋ฐฉ์ด ๋ฒฝ์ด๊ฑฐ๋ ์ฒญ์๊ฐ ๋์ด์๋ ๊ณณ์ด๋ผ๋ฉด ํ์ง์ ํ๋ค. ๊ทธ๋ฐ๋ฐ ํ์ง์ ํ ๊ณณ์ด ๋ฒฝ์ด๋ผ๋ฉด ์ฒญ์ ์์ ์ ์ข ๋ฃํ๋ค.
(๋ฐ๋ณต๋ฌธ ํ์ถํด์ ๊ฒฐ๊ณผ ์ถ๋ ฅ์ผ๋ก ์ด์ด์ง)
3. ์์ ์กฐ๊ฑด์ ๊ฑธ๋ฆฌ์ง ์์๋ค๋ฉด ๋ค ๋ฐฉํฅ ์ค ์ฒญ์ํ ๊ณณ์ด ๋จ์์๋ค๋ ๊ฒ์ด๋ค.
์ ์๋ฆฌ์์ ๋๋ฉด์ ๋ค ๋ฐฉํฅ ์ค ์ฒญ์ํ ๊ณณ์ ์ฐพ๊ณ , ์ฐพ์๋ค๋ฉด ๊ทธ ๋ฐฉํฅ์ผ๋ก ํ์ ํ ์ํ๋ก ๊ทธ ์นธ์ผ๋ก ์ด๋ํ๋ค.
4. ๋ค์ 1๋ฒ ์์ ๋ถํฐ ์์ํ๋ฉด์ 2๋ฒ์ ์ข ๋ฃ ์กฐ๊ฑด์ ๋ง์กฑํ ๋๊น์ง ๋ฐ๋ณต๋ฌธ์ ์ํํ๋ค.
์์ฑ ์ธ์ด: C++
#include <iostream>
#include <algorithm>
using namespace std;
int grid[51][51] = {0, };
int findNextDir(int dir) {
return (dir == 0) ? 3 : dir - 1;
}
int main() {
int n = 0, m = 0;
int r = 0, c = 0, dir = 0;
int cleans = 0;
// (๋ถ ๋ ๋จ ์) ๊ฐ ๋ฐฉํฅ ๊ธฐ์ค ์ข์ธก ์ขํ ์ด๋
int dr[4] = {0, -1, 0, 1};
int dc[4] = {-1, 0, 1, 0};
// read
cin >> n >> m;
cin >> r >> c >> dir;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> grid[i][j];
}
}
while (1) {
if (grid[r][c] == 0) {
// ํ์ฌ ์์น๊ฐ ์ฒญ์๊ฐ ์๋ ๊ณณ์ด๋ผ๋ฉด ์ฒญ์(์ฒญ์ํ๊ณ 2๋ก ํ์)
grid[r][c] = 2;
cleans += 1;
}
// ์ฌ๋ฐฉ์ด ์ฒญ์๋์๊ฑฐ๋ ๋ฒฝ์ธ ๊ฒฝ์ฐ ํ์ฌ ๋ฐฉํฅ์ ์ ์งํ๊ณ ํ์ง
if ((grid[r][c-1] == 1 || grid[r][c-1] == 2) && (grid[r][c+1] == 1 || grid[r][c+1] == 2) && (grid[r-1][c] == 1 || grid[r-1][c] == 2) && (grid[r+1][c] == 1 || grid[r+1][c] == 2)) {
if (dir == 0) r += 1; // ๋ถ์ชฝ์ ๋ณด๊ณ ์๋ค๋ฉด ํ ํ ์๋๋ก
else if (dir == 1) c -= 1; // ๋์ชฝ์ ๋ณด๊ณ ์๋ค๋ฉด ํ ์ด ์ผ์ชฝ์ผ๋ก
else if (dir == 2) r -= 1; // ๋จ์ชฝ์ ๋ณด๊ณ ์๋ค๋ฉด ํ ํ ์๋ก
else if (dir == 3) c += 1; // ์์ชฝ์ ๋ณด๊ณ ์๋ค๋ฉด ํ ์ด ์ค๋ฅธ์ชฝ์ผ๋ก
// ํ์งํ ๊ณณ์ด ๋ฒฝ์ด๋ฉด ์ ์ง
if (grid[r][c] == 1) break;
continue;
}
// ๋ค ๋ฐฉํฅ ์ค ์ฒญ์ํ ๊ณณ์ด ๋จ์์๋ ๊ฒฝ์ฐ
while (1) {
// ํ์ฌ ๋ฐฉํฅ ๊ธฐ์ค ์ข์ธก ์ขํ
int nr = r + dr[dir];
int nc = c + dc[dir];
// ์ข์ธก์ ์ฒญ์ํ ๊ณณ์ด ๋จ์์๋ค๋ฉด ๊ทธ ๋ฐฉํฅ์ผ๋ก ํ์ ํ๊ณ ์ด๋ํด์ ์ฒญ์ํ๊ณ ,
// ์ฒญ์ํ ๊ณณ์ด ์๋๋ผ๋ฉด ์ข์ธก์ผ๋ก ํ์ ํ๊ณ ๋ค์ ์์
์ํ
if (grid[nr][nc] == 0) {
r = nr; c = nc;
dir = findNextDir(dir);
break;
}else {
dir = findNextDir(dir);
}
}
}
cout << cleans << endl;
return 0;
}
๐ ๋ฐฐ์ด ์
์ด๋ฒ์ ์ฐํ ์ฝ(์ฐ์ํ ํ ํฌ ์ฝ์ค)์ ์ง์ํ๋ฉด์ ์ค๋ช ํ ์์์ด๋ ๊ฐ์ข ํ๊ธฐ๋ค์ ์ด์ฌํ ์ฐพ์๋ดค๋ค.
์ฝํ ์ ๋ ผ๋ฆฌ์ ์ธ ์ฌ๊ณ ๋ ฅ์ ์๊ตฌํ๋ ๋ฌธ์ ๋ค์ ์ถ์ ํ์ ๋ค๊ณ ํ๊ธธ๋ ๊ตฌํ ๋ฌธ์ ๋ฅผ ์ข ํ์ด๋ด์ผ ํ๋.. ์ถ์ด์ ๋ฐฑ์ค์์ ์ฒ์ ๋์ ํด๋ณด๋ ๊ตฌํ ๋ฌธ์ ์ด๋ค.
๋ฌธ์ ๋์ด๋์ ๋นํด ์๊ฐ์ ์ข ์ค๋ ์จ์ ๋๋ ๋ฐ๊ฐ ๋ง๋ค,,,
์ผ๋จ ์ฑ๊ธํ๊ฒ ์ ๊ทผํ์ง ๋ง๊ณ ๋จผ์ ํ ์คํธ์ผ์ด์ค๋ค์ ์ง์ ์๋ฒฝํ๊ฒ ํ์ด๋ด ๋ณด์!!(์ ๋ฐ๐ฑ)
๊ตฌํ ๋ฌธ์ ๋ ๋๋์ฑ ๋ฌธ์ ๋ฅผ ๊ผผ๊ผผํ ํ์ธํ๊ณ ์ง์ ์์ผ๋ก ํ์ด๋ณด๋ฉด์ ์์ธ์ฌํญ์ ์ ์ฒดํฌํ๋ ๊ฒ์ด ์ค์ํ ๊ฒ ๊ฐ๋ค.
'Problem_Solving' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ] ๋ฐฑ์ค 1647 ๋์ ๋ถํ ๊ณํ / ์ต์ ์ ์ฅ ํธ๋ฆฌ(MST), ํฌ๋ฃจ์ค์นผ (0) | 2020.11.20 |
---|---|
[BOJ] ๋ฐฑ์ค 1922 ๋คํธ์ํฌ ์ฐ๊ฒฐ / ์ต์ ์ ์ฅ ํธ๋ฆฌ(MST), ํฌ๋ฃจ์ค์นผ (0) | 2020.11.19 |
[BOJ] ๋ฐฑ์ค 2606 ๋ฐ์ด๋ฌ์ค / ๋๋น ์ฐ์ ํ์(BFS) (0) | 2020.11.05 |
[2020 KAKAO BLIND RECRUITMENT] ๋ฌธ์์ด ์์ถ (0) | 2020.09.01 |
[BOJ] ๋ฐฑ์ค 7576 ํ ๋งํ / ๋๋น ์ฐ์ ํ์(BFS) (0) | 2020.08.31 |