반응형
📖 문제
💡 풀이 방식
• DFS
(0, 0)에서부터 DFS 탐색을 시작한다.
해당 위치의 아래, 오른쪽 방향을 탐색하며
1) 격자 범위를 벗어나지 않고, 2) 방문한 적 없고, 3) 뱀이 없다면
해당 위치로 이동한다.
(N -1, M -1) 위치를 방문한 적 없다면 0을, 방문하였다면 1을 출력하도록 한다.
🔺 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
import java.util.*;
import java.io.*;
public class Main {
static int[] dx = {1, 0}; // 아래, 오른쪽
static int[] dy = {0, 1};
static int N, M;
static int[][] grid;
static boolean[][] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
grid = new int[N][M];
for(int i = 0 ; i < N ; i++) {
st = new StringTokenizer(br.readLine(), " ");
for(int j = 0 ; j < M ; j++) {
grid[i][j] = Integer.parseInt(st.nextToken());
}
}
visited = new boolean[N][M];
dfs(0, 0);
System.out.println(visited[N - 1][M - 1] ? 1 : 0);
}
private static void dfs(int x, int y) {
visited[x][y] = true; // 탐색 시작 전 해당 위치 방문했음 미리 표시
for(int d = 0 ; d < 2 ; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if(canGo(nx, ny)) {
dfs(nx, ny);
}
}
}
private static boolean canGo(int x, int y) {
if(!inRange(x, y) || visited[x][y]) return false;
if(grid[x][y] == 0) return false;
return true;
}
private static boolean inRange(int x, int y) {
return (0 <= x && x < N && 0 <= y && y < M);
}
}
|
cs |
➕ 다른 풀이 방식
visited 방문 배열을 boolean형으로 안 만들고, int형으로 만든다.
해당 위치를 방문했을 때는 1로 만들면 되고, grid[N - 1][M - 1]
을 출력해주면 된다.
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V |
(참고)
✔ 코드트리
그리드 상에서의 DFS 탐색 - 인접 리스트/행렬 필요 X
반응형
'코테 > 코드트리' 카테고리의 다른 글
[코드트리/INTERMEDIATE LOW] 숫자가 가장 큰 인접한 곳으로 동시에 이동 (JAVA) (0) | 2024.01.08 |
---|---|
[코드트리/INTERMEDIATE LOW] 뿌요뿌요 (JAVA) (0) | 2024.01.08 |
[코드트리/INTERMEDIATE LOW] 안전 지대 (JAVA) (0) | 2024.01.04 |
[코드트리/INTERMEDIATE LOW] 1차원 바람 (JAVA) (0) | 2024.01.03 |
[코드트리/INTERMEDIATE LOW] 트로미노 (JAVA) (0) | 2024.01.03 |