-
[백준 1261 - JAVA] 알고스팟Algorithm 2020. 11. 9. 19:13반응형
1261번: 알고스팟
첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미
www.acmicpc.net
풀이 방향을 맞게 잡았으나 조건을 잘못 넣어서 메모리 초과가 2번 났었다.
다익스트라인줄 몰랐으나 풀고보니 최소 횟수를 따라가며 갱신할 수 있을 때 큐에 삽입하는 다익스트라 방식으로 잘 풀었었다ㅎㅎ...
풀이 방법
-
벽을 뚫은 횟수(이하 cnt)를 저장할 2차원 배열(ans) 을 생성하고 큰값으로 초기화한다.
- 초기 장소인 0, 0 cnt는 0으로 배열을 만들어 cnt가 기준인 우선순위큐에 넣는다.
* 처음 장소는 항상 뚫려있다. -
큐가 빌때까지 bfs를 수행하는데 아래 조건을 충족한다.
- 벽을 만날 경우 cnt를 1 증가시킨다.
-
cnt가 ans에 저장된 횟수보다 작을 경우만 큐에 삽입한다.
import java.io.*; import java.util.*; public class Main { public static final int INF = Integer.MAX_VALUE/2; public static int N, M; public static int[][] map; public static int[][] ans; public static int[] dx = {-1, 1, 0, 0}; public static int[] dy = {0, 0, -1, 1}; public static void bfs() { PriorityQueue<int[]> que = new PriorityQueue<int[]>(new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { return Integer.compare(o1[2], o2[2]); } }); que.add(new int[] {0, 0, 0}); ans[0][0] = 0; while(!que.isEmpty()) { int[] cur = que.poll(); if (cur[2] > ans[cur[0]][cur[1]]) continue; for (int i = 0; i < 4; i++) { int nx = cur[0] + dx[i]; int ny = cur[1] + dy[i]; if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue; int cnt = cur[2]; if (map[nx][ny] == 1) cnt++; if (ans[nx][ny] > cnt) { ans[nx][ny] = cnt; que.add(new int[] {nx, ny, cnt}); } } } } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); M = Integer.parseInt(st.nextToken()); N = Integer.parseInt(st.nextToken()); map = new int[N][M]; ans = new int[N][M]; for (int i = 0; i < N; i++) { String line = br.readLine(); for (int j = 0; j < M; j++) { map[i][j] = line.charAt(j)-'0'; } } for (int[] arr : ans) { Arrays.fill(arr, INF); } bfs(); System.out.println(ans[N-1][M-1]); } }
'Algorithm' 카테고리의 다른 글
[백준 4386 - JAVA] 별자리 만들기 (0) 2020.11.12 [백준 1937 - JAVA] 욕심쟁이판다 (2) 2020.11.09 [백준 3108 - JAVA] 로고 (0) 2020.11.09 [SWEA 3234 - 준환이의 양팔저울] (0) 2020.11.09 [SWEA 4193 - JAVA] 수영대회 결승전 (0) 2020.11.09 -