반응형
단순 BFS 문제이다.
BFS 문제로는 어렵지 않다.
근데 나는 DFS로 풀고 싶은데 시간초과 안나게 어떻게 해야할지 모르겠다...
그리고 헷갈리는건 +1만 해주면 끝일까? Queue를 이용하기 때문에 먼저 방문한게 조금더 최단거리일려나? 음음
BFS 해결방법
1. 다음 방문할 점을 큐에 넣는다.
2. 큐에서 빼온다음 다음 갈 곳이 조건에 벗어나지 않는다면 큐에 넣는다.
3. 큐가 빌때까지 계속한다. ( 내가 원하는 점에 왔을때 return 해줘도 가능하지 않을까? 개인적인 생각)
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 64 65 66 67 68 69 70 71 72 73 | import java.io.FileInputStream; import java.util.*; public class Main { static int[][] arr; static boolean[][] visited; static int[] dx = { -1, 0, 1, 0 }; static int[] dy = { 0, -1, 0, 1 }; static int N; static int M; public static void main(String args[]) throws Exception { // Scanner sc = new Scanner(System.in); Scanner sc = new Scanner(new FileInputStream("input.txt")); N = sc.nextInt(); M = sc.nextInt(); sc.nextLine(); arr = new int[N][M]; visited = new boolean[N][M]; for (int i = 0; i < N; i++) { String str = sc.nextLine(); for (int j = 0; j < M; j++) { arr[i][j] = str.charAt(j)-'0'; visited[i][j] = false; } } visited[0][0] = true; BFS(0, 0); System.out.println(arr[N - 1][M - 1]); } static public void BFS(int x, int y) { Queue<Dot> q = new LinkedList<Dot>(); q.add(new Dot(x, y)); //큐가 끝날때 까지 while (!q.isEmpty()) { Dot d = q.poll(); for (int i = 0; i < 4; i++) { //다음 방문할 좌표 nextX, nextY int nextX = d.x + dx[i]; int nextY = d.y + dy[i]; //다음 좌표가 범위를 넘어갈때 건너뛰기 if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) { continue; } //이미 방문했던 점이면 건너뛰기 if (visited[nextX][nextY] || arr[nextX][nextY] == 0) { continue; } //다음에 방문할 좌표를 큐에 넣는다. q.add(new Dot(nextX, nextY)); //배열안에 다음 방문할 곳은 현재 방문했던 점보다 1칸 더 가야하므로 +1 arr[nextX][nextY] = arr[d.x][d.y] + 1; //다음 좌표는 방문했음으로 표시 visited[nextX][nextY] = true; } } } } class Dot { int x; int y; Dot(int x, int y) { this.x = x; this.y = y; } } | cs |
반응형
'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글
[BOJ] 백준 1012 - 유기농 배추 (자바) (0) | 2018.02.03 |
---|---|
[BOJ] 백준 1475 - 방 번호 (자바) (0) | 2018.01.30 |
[BOJ] 백준 5598 - 카이사르 (자바) (0) | 2018.01.22 |
[BOJ] 백준 2839 - 설탕배달 (자바) (0) | 2018.01.22 |
[BOJ] 백준 10815 - 숫자카드 (자바) (0) | 2018.01.22 |