์ ๋ช ํ ์ ๋นต์ฌ ๊น์์ ์ ๋นต์ง์ ์ด์ํ๊ณ ์๋ค. ์์ ์ด์ ๋นต์ง์ ๊ธ๋ก๋ฒ ์ฌ์ ์๊ธฐ๋ฅผ ํผํด๊ฐ์ง ๋ชปํ๊ณ , ๊ฒฐ๊ตญ ์ฌ๊ฐํ ์ฌ์ ์๊ธฐ์ ๋น ์ก๋ค.
์์ ์ด๋ ์ง์ถ์ ์ค์ด๊ณ ์ ์ฌ๊ธฐ์ ๊ธฐ ์ง์ถ์ ์ดํด๋ณด๋ ์ค์, ๊ฐ์ค๋น๊ฐ ์ ์ผ ํฌ๋ค๋ ๊ฒ์ ์๊ฒ๋์๋ค. ๋ฐ๋ผ์ ์์ ์ด๋ ๊ทผ์ฒ ๋นต์ง์ ๊ฐ์ค๊ด์ ๋ชฐ๋ ํ์ดํ๋ฅผ ์ค์นํด ํ์ณ์ ์ฌ์ฉํ๊ธฐ๋ก ํ๋ค.
๋นต์ง์ด ์๋ ๊ณณ์ R*C ๊ฒฉ์๋ก ํํํ ์ ์๋ค. ์ฒซ์งธ ์ด์ ๊ทผ์ฒ ๋นต์ง์ ๊ฐ์ค๊ด์ด๊ณ , ๋ง์ง๋ง ์ด์ ์์ ์ด์ ๋นต์ง์ด๋ค.
์์ ์ด๋ ๊ฐ์ค๊ด๊ณผ ๋นต์ง์ ์ฐ๊ฒฐํ๋ ํ์ดํ๋ฅผ ์ค์นํ๋ ค๊ณ ํ๋ค. ๋นต์ง๊ณผ ๊ฐ์ค๊ด ์ฌ์ด์๋ ๊ฑด๋ฌผ์ด ์์ ์๋ ์๋ค. ๊ฑด๋ฌผ์ด ์๋ ๊ฒฝ์ฐ์๋ ํ์ดํ๋ฅผ ๋์ ์ ์๋ค.
๊ฐ์ค๊ด๊ณผ ๋นต์ง์ ์ฐ๊ฒฐํ๋ ๋ชจ๋ ํ์ดํ๋ผ์ธ์ ์ฒซ์งธ ์ด์์ ์์ํด์ผ ํ๊ณ , ๋ง์ง๋ง ์ด์์ ๋๋์ผ ํ๋ค. ๊ฐ ์นธ์ ์ค๋ฅธ์ชฝ, ์ค๋ฅธ์ชฝ ์ ๋๊ฐ์ , ์ค๋ฅธ์ชฝ ์๋ ๋๊ฐ์ ์ผ๋ก ์ฐ๊ฒฐํ ์ ์๊ณ , ๊ฐ ์นธ์ ์ค์ฌ๋ผ๋ฆฌ ์ฐ๊ฒฐํ๋ ๊ฒ์ด๋ค.
์์ ์ด๋ ๊ฐ์ค๋ฅผ ๋๋๋ก ๋ง์ด ํ์น๋ ค๊ณ ํ๋ค. ๋ฐ๋ผ์, ๊ฐ์ค๊ด๊ณผ ๋นต์ง์ ์ฐ๊ฒฐํ๋ ํ์ดํ๋ผ์ธ์ ์ฌ๋ฌ ๊ฐ ์ค์นํ ๊ฒ์ด๋ค. ์ด ๊ฒฝ๋ก๋ ๊ฒน์น ์ ์๊ณ , ์๋ก ์ ํ ์๋ ์๋ค. ์ฆ, ๊ฐ ์นธ์ ์ง๋๋ ํ์ดํ๋ ํ๋์ด์ด์ผ ํ๋ค.
์์ ์ด ๋นต์ง์ ๋ชจ์ต์ด ์ฃผ์ด์ก์ ๋, ์์ ์ด๊ฐ ์ค์นํ ์ ์๋ ๊ฐ์ค๊ด๊ณผ ๋นต์ง์ ์ฐ๊ฒฐํ๋ ํ์ดํ๋ผ์ธ์ ์ต๋ ๊ฐ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ R๊ณผ C๊ฐ ์ฃผ์ด์ง๋ค. (1 โค R โค 10,000, 5 โค C โค 500)
๋ค์ R๊ฐ ์ค์๋ ๋นต์ง ๊ทผ์ฒ์ ๋ชจ์ต์ด ์ฃผ์ด์ง๋ค. '.'๋ ๋น ์นธ์ด๊ณ , 'x'๋ ๊ฑด๋ฌผ์ด๋ค. ์ฒ์๊ณผ ๋ง์ง๋ง ์ด์ ํญ์ ๋น์ด์๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ์์ ์ด๊ฐ ๋์ ์ ์๋ ํ์ดํ๋ผ์ธ์ ์ต๋ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค.
๐ก ์ ํ์ ์ธ ๋ฐฑํธ๋ํน
๐ก dfs๋ก ํ์ดํ๋ฅผ ๋ชจ๋ ๊ฒฝ์ฐ ํ์ํด์ผํจ
๐ก ์ด๋ฏธ ๋ฐฉ๋ฌธํ ๊ณณ์ x๋ก ๋ฐ๊ฟ ๊ฐ์ง ๋ชปํ๊ฒ ํจ (๊ธฐ์กด์ visited๋ ๋น์ทํ ์ญํ )
๐ก boolean ๋ณ์๋ฅผ ์ง์ ํด ์ด๋ฏธ ํ์ดํ๊ฐ ์๋ ๊ณณ์์ ๋ค๋ฅธ ๊ณณ์ผ๋ก ํ์๋๋ ๊ธธ์ ๋ง์์ผํจ
if(col == c-1) {
connect = true;
cnt++;
return;
}
map[row][col] = 'x';
if(connect) {
return;
}
import java.io.*;
public class BOJ_3109 {
static char[][] map;
static int r, c, cnt = 0;
static int[] dr = {-1,0,1};
static boolean connect;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] s = br.readLine().split(" ");
r = Integer.parseInt(s[0]);
c = Integer.parseInt(s[1]);
map = new char[r][c];
for(int i=0; i<r; i++) {
map[i] = br.readLine().toCharArray();
}
for(int i=0; i<r; i++) {
connect = false;
dfs(i, 0);
}
StringBuilder sb = new StringBuilder();
sb.append(cnt);
bw.write(sb.toString());
bw.flush();
}
static void dfs(int row, int col) {
if(col == c-1) {
connect = true;
cnt++;
return;
}
for(int i=0; i<3; i++) {
int nc = col + 1;
int nr = row + dr[i];
if(nr < 0 || nr >= r || nc < 0 || nc >= c)
continue;
if(map[nr][nc] == '.') {
map[row][col] = 'x';
dfs(nr, nc);
if(connect) {
return;
}
}
}
}
}
์ฑ๊ณตโจ