Menu

Subscribe

[JAVA/백준] SW 역량 테스트 준비-기초 | 그래프와 BFS: 알고스팟

HEESOO on Boj

👀 문제

https://www.acmicpc.net/problem/1261

👊 도전

1. 설계

  1. BFS를 이용하는 대신, 일반 큐가 아닌 우선순위큐를 이용하여 먼저 방문할 노드들을 결정해준다.
  2. 먼저 방문해야할 노드는, 벽 부순 횟수(cnt)가 작은 순이다.

2. 구현 (성공 코드)

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

import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * @author HEESOO
 *
 */
public class Main {
	public static int bfs(int n, int m, int[][] map) {
		PriorityQueue<Dot> q=new PriorityQueue<>();
		q.offer(new Dot(0,0,0));
		int[] dotX= {1,0,-1,0};
		int[] dotY= {0,1,0,-1};
		boolean[][] visit=new boolean[n][m];
		visit[0][0]=true;
		
		while(!q.isEmpty()) {
			Dot dot=q.poll();
			if(dot.x==n-1 && dot.y==m-1) return dot.cnt;
			for(int i=0;i<4;i++) {
				int xx=dot.x+dotX[i];
				int yy=dot.y+dotY[i];
				if(0<=xx&&xx<n && 0<=yy&&yy<m && !visit[xx][yy]) {
					visit[xx][yy]=true;
					if(map[xx][yy]==1) 
						q.offer(new Dot(xx, yy, dot.cnt+1));
					else 
						q.offer(new Dot(xx, yy, dot.cnt));
				}
			}
		}
		return -1;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan=new Scanner(System.in);
		int m=scan.nextInt();
		int n=scan.nextInt();
		int[][] map=new int[n][m];
		for(int i=0;i<n;i++) {
			String str=scan.next();
			for(int j=0;j<m;j++) {
				map[i][j]=str.charAt(j)-'0';
			}
		}
		
		System.out.println(bfs(n, m, map));
	}
}
class Dot implements Comparable<Dot>{
	int x;
	int y;
	int cnt;
	public Dot(int x, int y, int c) {
		this.x=x;
		this.y=y;
		this.cnt=c;
	}
	@Override
	public int compareTo(Dot target) {
		if(this.cnt<target.cnt) return -1;
		else if(this.cnt==target.cnt) return 0;
		else return 1;
	}
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. BFS를 이용한다
    • (0,0)에서 (n-1, m-1)까지 가기 위해 상하좌우로 움직이면서 방문하지 않은 곳이라면(!visit[xx][yy]) 큐에 넣는다. 이때 벽이라면(map[xx][yy]==1) dot(현재 위치).cnt+1로 벽을 부순 횟수를 하나 증가시키고, 아니라면 현재까지 부순 횟수를 가지고 new Dot을 생성하여 큐에 집어 넣는다.
  2. PriorityQueue를 이용한다
    • 단순히 최단 경로를 구하는 것이 아니라, 최단 경로로 가면서 벽을 가장 덜 부수는 방법을 찾아야 하므로 큐에서 우선순위 설정이 필요하다.
    • 큐에 Dot 클래스를 넣을 것이므로, 해당 클래스에서 compareTo()를 Override하여 우선순위를 지정해준다.
    • 벽을 부순 횟수가 작을수록 더 큰 우선순위를 가진다(먼저 큐에서 빠져나와야하므로 앞으로 이동해야한다.)
    • 나(this)와 비교 대상(target)를 두고, 내 cnt(현재 위치까지의 벽을 부순 횟수)가 더 작을 때 -1을 리턴하여 앞으로 이동한다. 같다면 그대로(0), target.cnt가 더 작다면 나는 뒤로 가야 하므로 1을 리턴한다.

👏 해결 완료!