-
[1261] 알고스팟 - Java[자바]자바/백준 2023. 9. 17. 21:57
| 문제 링크
https://www.acmicpc.net/problem/1261
1261번: 알고스팟
첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미
www.acmicpc.net
| 문제
- 첫째 줄에 N(열)과 M(행)이 주어집니다.
- 그 다음 M줄에 줄마다 N개의 숫자가 들어옵니다.
0(빈 칸) 또는 1(벽) - 1,1 부터 N,M 까지 이동하기까지 벽을 최소 몇 개 부수어야 하는지 출력하시오.
| 풀이
- 맨 처음에는 일반적인 bfs에 사방 탐색으로 벽으로 막혀있는 경우에는 길을 뚫고 bfs를 이어갈 생각이었으나. 아래와 같은 반례에 막혀 데이크스트라(다익스트라라고도 불림)라는 알고리즘을 배우게 됐습니다.
4 4
0011
1111
0111
0000
answer : 1
wrong answer : 2 - 데이크스트라와 bfs의 차이점과 공통점은 다음과 같다.
공통점: 너비 우선 탐색으로 최단 경로를 찾는데 주로 사용된다.
차이점: bfs는 노드간 가중치가 없고(일반 Queue를 사용), 데이크스트라는 노드간 가중치를 두어(PriorityQueue를 사용) 가중치가 높은 너비를 우선 탐색한다. - 좌표와 가중치(벽을 한 번 부술 때 마다 가중치 +1)를 멤버 변수로 가지는 Node 클래스를 만들며, PriorityQueue(이하 pQue)에서 Node 값으로 정렬되기 위해 Comparable 인터페이스를 implements해줍니다.
- 입력 받은 미로의 크기와 동일한 크기의 배열(weight)을 Integer.MAX_VALUE로 채우고 탐색하는 좌표의 가중치를 관리할 준비를 합니다.
- 일반적인 bfs와 동일하게 1,1의 좌표 값과 가중치 0(첫 시작에는 빈 칸임을 문제에서 주어줌)을 pQue에 넣고 pQue가 공란이 될 때 까지 반복문을 동작합니다.
- N,M 까지 너비 우선 탐색을 해주며, 벽(=1)을 만나는 경우 가중치를 +1 해주며 pQue에 넣고 weight 배열의 해당 좌표에 입력된 가중치보다 작은 경우 weight의 가중치를 해당 가중치로 바꿉니다.
- 벽을 만나지 않는 경우에는 가중치를 증가시키지 않고 좌표와 함께 pQue에 넣어줍니다.
- weight 배열의 N,M의 값을 출력합니다.
| 코드
import java.io.*; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main { public static int n; public static int m; public static int[][] maze; public static int[][] weight; public static int[][] delta = {{-1,0},{0,1},{1,0},{0,-1}}; public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); 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()); maze = new int[m][n]; weight = new int[m][n]; for(int r = 0; r<m; r++) { String str = br.readLine(); for(int c = 0; c<n; c++) { maze[r][c]=str.charAt(c)-'0'; weight[r][c]=Integer.MAX_VALUE; } } if(n==1 && m==1) bw.write("0"); else { dijkstra(); bw.write(String.valueOf(weight[m-1][n-1])); } br.close(); bw.close(); } public static void dijkstra() { PriorityQueue<Node1261> pQue = new PriorityQueue<>(); pQue.add(new Node1261(0,0,0)); weight[0][0]=0; while(!pQue.isEmpty()) { Node1261 rc = pQue.poll(); for(int i = 0; i<4; i++) { int dr = rc.r+delta[i][0]; int dc = rc.c+delta[i][1]; int wall = rc.wall; //인덱스의 범위를 벗어나는 경우 continue if(dr<0 || dr>=m || dc<0 || dc>=n) continue; if(maze[dr][dc]==1) wall++; if(weight[dr][dc]>wall) { weight[dr][dc] = wall; pQue.add(new Node1261(dr,dc,wall)); } } } } //노드를 생성해 각 좌표를 관리하며, PriorityQueue에 넣기 위해 정렬 기준을 설정한다. public static class Node1261 implements Comparable<Node1261>{ int r; int c; int wall; public Node1261(int r, int c, int wall) { super(); this.r = r; this.c = c; this.wall = wall; } //Node1261끼리 정렬할 경우 wall 값의 오름차순으로 정렬 public int compareTo(Node1261 o) { return this.wall-o.wall; } } }
'자바 > 백준' 카테고리의 다른 글
[1766] 문제집 - Java[자바] (0) 2023.09.22 [5675] 음주 코딩 - Java[자바] (0) 2023.09.22 [1976] 여행 가자 - Java[자바] (2) 2023.09.16 [1520] 내리막 길 - Java[자바] (0) 2023.09.13 [2206] 벽 부수고 이동하기 - Java[자바] (0) 2023.09.13