반응형
📖 문제
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
💡 풀이 방식
• BFS
필요 자료구조
- 인접 4방향 탐색용 dx/dy 배열
- 숫자 입력받을 2차원 int형 배열 (grid)
- 방문 여부 표시할 2차원 int형 배열 (visited)
- 방문하는 칸 위치 저장할 Queue
(0, 0)부터 BFS를 수행한다.
BFS 수행 시, 큐에 해당 위치 좌표를 저장하고, 방문 처리(visited[x][y] = 1)한다.
위치를 저장한 큐가 모두 빌 때까지 큐에서 위치를 뽑는다.
뽑은 위치의 인접 4방향을 탐색하며
1) 격자 범위를 벗어나지 않고 2) 방문한 적 없고 3) 뱀이 아닌 경우 (1인 경우)
해당 좌표에서 다음 탐색을 진행하도록 그 위치 값을 큐에 저장한다.
탈출 가능한 경로가 있다면 맨 오른쪽 아래 칸의 값도 1일 것이며,
없다면 맨 오른쪽 아래 칸의 값은 0일 것이므로
맨 오른쪽 아래 칸의 값을 그대로 출력한다.
(문제 조건에 끝 칸에는 뱀이 주어지지 않는다고 가정한다 하였으므로 가능)
🔺 코드
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
57
58
59
60
61
62
63
|
import java.util.*;
import java.io.*;
public class Main {
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static int N, M;
static int[][] grid;
static int[][] 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 int[N][M];
bfs(0, 0);
System.out.println(visited[N- 1][M - 1]);
}
private static void bfs(int x, int y) {
Queue<int[]> q = new ArrayDeque<>();
q.add(new int[] {x, y});
visited[x][y] = 1;
while(!q.isEmpty()) {
int[] now = q.poll();
for(int d = 0 ; d < 4 ; d++) {
int nx = now[0] + dx[d];
int ny = now[1] + dy[d];
if(canGo(nx, ny)) {
q.add(new int[] {nx, ny});
visited[nx][ny] = 1;
}
}
}
}
private static boolean canGo(int x, int y) {
if(!inRange(x, y)) return false;
if(visited[x][y] == 1 || 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 |
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V |
반응형
'코테 > 코드트리' 카테고리의 다른 글
[코드트리/INTERMEDIATE LOW] 갈 수 있는 곳들 (JAVA) (0) | 2024.01.08 |
---|---|
[코드트리/INTERMEDIATE LOW] 숫자의 순차적 이동 (JAVA) (1) | 2024.01.08 |
[코드트리/INTERMEDIATE LOW] 숫자가 가장 큰 인접한 곳으로 동시에 이동 (JAVA) (0) | 2024.01.08 |
[코드트리/INTERMEDIATE LOW] 뿌요뿌요 (JAVA) (0) | 2024.01.08 |
[코드트리/INTERMEDIATE LOW] 두 방향 탈출 가능 여부 판별하기 (JAVA) (0) | 2024.01.07 |