풀이 방법
최단 경로를 찾는 문제가 아닌 겹치지 않는 모든 경로를 찾는 문제이다.
위에서부터 탐색해서 경로를 찾으면 return 시켜주는 방식으로 풀이했고 경로를 찾지 못하게 되면 visited를 false로 바꾸는 것이 아니라 그 길로 가게되면 경로를 찾을 수 없기 때문에 true 상태로 남겨두었습니다.
내 코드
import java.io.*;
import java.util.*;
public class Main {
static char[][] arr;
static int R, C, count;
static int[] direct = { -1, 0, 1 };
static boolean[][] visited;
static boolean check;
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());
count = 0;
arr = new char[R][C];
visited = new boolean[R][C];
for (int i = 0; i < R; i++) {
String s = br.readLine();
for (int j = 0; j < C; j++) {
arr[i][j] = s.charAt(j);
}
}
for (int i = 1; i < R; i++) {
if(arr[i][0] == '.') {
check = false;
dfs(i, 0);
}
}
System.out.println(count);
}
static void dfs(int x, int y) {
if (y == C - 2) {
count++;
check = true;
return;
}
for (int i = 0; i < 3; i++) {
int nextX = x + direct[i];
int nextY = y + 1;
if (nextX >= 0 && nextX < R && arr[nextX][nextY] == '.' && !visited[nextX][nextY]) {
visited[nextX][nextY] = true;
dfs(nextX, nextY);
if (check) {
return;
}
}
}
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
아기 상어 - 16236번 (0) | 2022.02.23 |
---|---|
감시 - 15683번 (0) | 2022.02.18 |
가장 가까운 공통 조상 - 3584번 (0) | 2022.02.15 |
모래성 - 10711번 (0) | 2022.02.14 |
스타트링크 - 5014번 (0) | 2022.02.14 |