Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 1032
- 크레인인형뽑기게임
- 백준
- jvm
- Baekjoon
- 병합정렬
- 프로그래머스
- 스웨거
- java
- 6236
- vue3
- 수들의 합
- springboot
- 용돈관리
- 자바
- vue-cli
- swagger3
- 대충 만든 자판
- Di
- IoC container
- 2178
- 추억점수
- 헤이로라
- getOrDefault
- Spring Security
- docker
- Spring
- call by value
- 2751
- springdoc
Archives
- Today
- Total
개발쿠키
[백준]2178 - 미로 탐색(Java) 본문
https://www.acmicpc.net/problem/2178
풀이
최소 길이를 구하라는 것을 보고 BFS로 고고
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
//2178번
public class FindMaze {
static int N, M;
static int[] dx = {-1, 1, 0, 0 };
static int[] dy = {0 , 0, -1, 1};
static int[][] map;
static int[][] dis;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
map = new int[N][M];
dis = new int[N][M];
int max = 0;
for (int i = 0; i < N; i++) {
String s = sc.next();
for (int j = 0; j < M; j++) {
map[i][j] = Character.getNumericValue(s.charAt(j));
}
}
//시작
BFS(0,0);
System.out.println(dis[N-1][M-1] + 1);
}
public static void BFS(int x, int y) {
Queue<Point> Q = new LinkedList<>();
//최초 받은 0,0 offer
Q.offer(new Point(x, y));
//진입 불가 처리
map[x][y] = 0;
//BFS
while (!Q.isEmpty()) {
Point tmp = Q.poll();
for (int i = 0; i < 4; i++) {
int nx = tmp.x + dx[i];
int ny = tmp.y + dy[i];
//이동했을 때 x,y 값이 0보다 커야하고 사이즈보다 작아야 하며 갈 수 있는 길(1)이어야함
if (nx >= 0 && ny >= 0 && nx < N && ny < M && map[nx][ny] == 1) {
//이미 간 곳은 막음
map[nx][ny] = 0;
Q.offer(new Point(nx, ny));
//거리 표시
dis[nx][ny] = dis[tmp.x][tmp.y] + 1;
}
}
}
}
static class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}
'개발 > baekjoon&programmers' 카테고리의 다른 글
[백준]6236 용돈관리 (0) | 2024.02.16 |
---|---|
[백준]2751 - 병합정렬(Java) (2) | 2023.10.25 |
[백준] 수들의 합(Java) (0) | 2023.10.10 |
[프로그래머스]신규 아이디 추천 (0) | 2023.09.21 |
[프로그래머스]대충 만든 자판 (0) | 2023.08.16 |