1. ๋ฌธ์ ์ ๋ํ์ฌ ๐ฆ
- ๋ฌธ์ ๋งํฌ: https://www.acmicpc.net/problem/3109
(1) ์กฐ๊ฑด ๋ถ์ ๐
์ฒซ ๋ฒ์งธ ์ด๋ถํฐ ์์ํด์ ๋ง์ง๋ง ์ด๊น์ง ์ด์ ์ ์๋ ๊ฒฝ๋ก์ ๊ฐ์๋ฅผ ๊ตฌํ๋ผ.
๊ฒฝ๋ก๋ฅผ ์๋ ํ์ดํ๋ผ์ธ์ /, -, \ (๋๊ฐ์ ์๋จ, ์ผ์ ๊ฐ๋ก, ๋๊ฐ์ ํ๋จ)์ผ๋ก ๋ฐ์ ๋ชปํ๋ค.
2. ์ฝ๋๊ฐ ๋์ค๊ธฐ๊น์ง ๐ ๏ธ
KEY WORD: ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ, ๋ฐฑํธ๋ํน, ์ ๋ ฌ
๋นต์ง ๊ฐ์ค๊ด์์์ ์ถ๋ฐ์ง๋ ๋๋๋ก ๋งจ ์์์ ์ถ๋ฐํด์ ๋์ฐฉ์ง ๋ํ ๋๋๋ก ์๋จ์ ์๋ ๊ณณ์ผ๋ก ๋์ฐฉํ๋ ค ํด์ผ ํ๋ค. ์ด์ ๋ ๋ค์๊ณผ ๊ฐ๋ค.
- ์ต๋ํ ์๋จ์ ์๋ ๊ฒ์ ๊ณจ๋ผ์ค์ผ ์ถํ ๊ฐ์ค๊ด ์ถ๋ฐ์ง์์ ๊ฐ ์ ์๋ ๋์ฐฉ์ง์ ๋ฒ์๊ฐ ๋์ด์ง๋ค.
- ๋์ฐฉ์ง์ ๋ฒ์๊ฐ ๋์ด์ง์๋ก ๋ ๋ง์ ๊ฒฝ๋ก๋ฅผ ๊ฐ์ง ์ ์๋ค.
์์ 2๊ฐ์ง ๋๋ฌธ์ ํด๋น ๋ฌธ์ ๋ ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ํธ๋ ๋ฌธ์ ์ด๋ค. ์ต๋ํ ์๋จ์ผ๋ก ๊ฐ๋ณด๊ณ ์๋๋ฉด, ๋๋จธ์ง ๊ฒฝ๋ก๋ฅผ ํ์ํ๋ค. ๋ํ ๋ค์ ๊ฒฝ๋ก๊ฐ ๋๋์ง ์๋๋์ง ํ์ธํ๊ธฐ ๋๋ฌธ์ ๋ฐฑํธ๋ํน์ด๋ผ๊ณ ๋ ๋ณผ ์ ์๋ค.
(1) ์ค๋ณต ํ์ ๋ฐฉ์ง
๋ชฉ์ ์ง ๋๋ฌ ์คํจ ๊ฒฝ๋ก์ด๋ ์ฑ๊ณต ๊ฒฝ๋ก์ด๋ ๋ฐฉ๋ฌธ ํ์ ์ ๋จ๊ฒจ ๋ค์ ์ถ๋ฐ์ง์์ ๋์ผํ ์์น๋ก ๊ฐ์ง ๋ชปํ๊ฒ ํ๋ค.
- ์ด์ ๊ฒฝ๋ก๊ฐ ์คํจํ ๊ฒฝ๋ก๋ผ๋ฉด, ์คํจํ ๋ฃจํธ๋ฅผ ๊ทธ๋๋ก ๋ฐ๋ผ๊ฐ๋ ๊ณ์ฐ ์๊ฐ ๋ญ๋น๋ฅผ ์ค์ธ๋ค.
- ์ด์ ๊ฒฝ๋ก๊ฐ ์ฑ๊ณตํ ๊ฒฝ๋ก๋ผ๋ฉด, ์ค๋ณต๋ ๊ฒฝ๋ก ํ์ ์๊ฐ ๋ญ๋น๋ฅผ ์ค์ธ๋ค.
(2) ์๊ฐ๋ณต์ก๋ ๋ถ์ โณ
๋ง์ฝ ํด๋น ๋ฌธ์ ๋ฅผ ์์ ํ์์ผ๋ก ํ์๋ค๋ฉด, ์ขํ ํ๋๋น ์ ํ์ง๊ฐ 3๊ฐ์ด๋ฏ๋ก, $3^{(R \times C)}$ ๋ฒ์ด๋ค. R์ด ์ต๋ $10,000$๊ฐ, C๊ฐ ์ต๋ $500$ ๊ฐ์ด๋ฏ๋ก ์๊ฐ์ด๊ณผ๊ฐ ๋๋ค. ํ์ง๋ง ์์ ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ + ๋ฐฑํธ๋ํน์ผ๋ก ๋ฌธ์ ๋ฅผ ํ๋ฉด, ์ค๋ณต ํ์ ์๊ฐ์ ์ค์ด๋ฏ๋ก ์๊ฐ์ ์ด๋์ ๋ณผ ์ ์๋ค.
3. ์ฝ๋ ๐
(1) SUDO CODE ๐ฌ
// ๊ฐ๋จํ ์์ฌ ์ฝ๋
1. ์
๋ ฅ ๋ฐ๊ธฐ
2. (0,0) ์ขํ๋ถํฐ ๋๊ฐ ์๋จ, ๊ฐ๋ก ์ผ์, ๋๊ฐ ํ๋จ ์์ผ๋ก DFS
3. ๋ง์ฝ ๊ฒฝ๋ก๋ฅผ ๋ฐ๊ฒฌํ๋ค๋ฉด ๊ณ์ฐ์ ๋ฉ์ถ๊ณ ๋ค์ ์ขํ๋ก ๋์ด๊ฐ๋ค.
4. ๊ฒฝ๋ก๋ฅผ ๋ฐ๊ฒฌํ์ง ๋ชปํ๋ค๋ฉด, ์คํจ ๊ฒฝ๋ก๋ฅผ ์ต๋ํ ์ฐพ์์ ๋ค์ ๊ณ์ฐ ์ค๋ณต์ ์ค์ธ๋ค.
(2) JAVA CODE โ
import java.util.*;
import java.io.*;
// b 3109 ๋นต์ง
public class Main {
static int R,C;
static char [][] map;
static int [] dir = new int [] {-1,0,1};
static int pipe = 1;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
map = new char[R][C];
for(int i = 0; i < R; i++){
String row = br.readLine();
for (int j = 0; j < C; j++){
map[i][j] = row.charAt(j);
} } int answer = 0;
for(int i = 0; i < R; i++){
if(dfs(i,0)) answer++;
}
System.out.println(answer);
} public static boolean dfs(int r, int c){
// ๊ธฐ์ ์กฐ๊ฑด
if(c == C-1) {
map[r][c] = 'H';
pipe++;
return true;
}
for (int i = 0; i < 3; i++) {
int nr = r + dir[i];
int nc = c + 1;
if(OOB(nr,nc)) continue;
if(map[nr][nc] != '.') continue;
map[r][c] = (char) (pipe+'0');
if(dfs(nr,nc)) return true;
} return false;
}
public static boolean OOB(int r, int c){
return r < 0 || c < 0 || r >= R || c >= C;
}
}
4. ํธ๋ฌ๋ธ ์ํ or ๋ฐฐ์ด ์ ๐
๋ฌธ์ ํธ๋ ๊ฐ์ด ์ ์กํ์ ๋ต์ง๋ฅผ ๋ดค๋ค. ๋ค์์ ๋ค์ ํ์ด๋ด์ผ๊ฒ ๋ค.
4%์์ ํ๋ฆฌ๋ฉด ํด๋ด์ผํ ๋ฐ๋ก
15 15
.xxxxxxxxxx....
...x.......xxx.
...x.......x...
..xx.......xx..
...x........xx.
.x.x......x.x..
...x......xx...
.x.x....xxx....
.x....x.x......
.x.....xx.x....
.x..x.xx.......
.....xx........
....x..........
......x........
...............
---
// ๋ต: 4