문제 링크
https://www.acmicpc.net/problem/17086
나의 기록
✅ 알고리즘 분류 : BFS
✅ 성공 여부 : ✔
✅ 문제 난이도 : 실버1
✅ 체감 난이도 : Normal
접근 방법
평범한 2차원 배열 탐색 문제에 함정 살짝 추가한 느낌.
DFS로는 시간초과 나고 BFS로 시간초과 없이 풀린다.
도착점에 도착했을 경우 바로 탈출해야 하며, 그렇지 않을 경우 불필요한 추가 탐색으로 오답이 나온다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class bj2178_미로탐색 {
static class Point{
int x,y,dist;
public Point(int x, int y, int dist) {
this.x = x;
this.y = y;
this.dist = dist;
}
}
static int[] di = {0,0,-1,1};
static int[] dj = {-1,1,0,0};
static int N,M, ans = 0;
static int[][] map;
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());
map = new int[N+1][M+1];
for(int i = 1 ; i <= N ; i++){
String str = br.readLine();
for(int j = 1 ; j <= M ; j++){
map[i][j] = str.charAt(j-1) - '0';
}
}
// BFS
bfs();
// 출력
System.out.println(ans);
}
public static void bfs() {
Queue<Point> queue = new LinkedList<>();
queue.add(new Point(1, 1, 1));
boolean[][] visited = new boolean[N + 1][M + 1];
visited[1][1] = true;
while (!queue.isEmpty()) {
Point now = queue.poll();
ans = now.dist;
// 이미 도착점에 도착해 더 진행할 필요가 없을 경우
if (now.x == N && now.y == M) {
break;
}
// 4방향 탐색
for (int d = 0; d < 4; d++) {
int nx = now.x + di[d];
int ny = now.y + dj[d];
if (isValid(nx, ny) && !visited[nx][ny]) {
queue.add(new Point(nx, ny, now.dist + 1));
visited[nx][ny] = true;
}
}
}
}
public static boolean isValid(int x, int y){
return x >= 1 && x <= N && y >= 1 && y <= M && map[x][y] == 1;
}
}
'알고리즘 (Java)' 카테고리의 다른 글
(Java) 백준 1283 단축키 지정 (0) | 2023.03.22 |
---|---|
(Java) 백준 10808 스택 (0) | 2023.03.22 |
(Java) 백준 17086 아기 상어 2 (0) | 2023.03.10 |
(Java) 백준 11403 경로 찾기 (0) | 2023.03.09 |
(Java) 백준 2667 단지번호붙이기 (0) | 2023.03.08 |