[백준] 1445 일요일 아침의 데이트

1. 문제

www.acmicpc.net/problem/1445

1445번: 일요일 아침의 데이트

2. 접근방법

pq를 안다면 간단히 해결되는 문제

쓰레기가 최소가 되면서 그 다음으로 쓰레기 주변이 최소가 되면서 꽃에 도달하는 경로를 찾는 문제

 

먼저 쓰레기의 주변이지 확인하는 것을 쉽게하려고

쓰레기의 4방에 b라는 문자를 넣었다.

 

그 다음 시작위치부터 bfs로 돌아가는데 지금까지 온 경로중

1. 쓰레기를 가장 적게 지나왔고

2. 그 중 쓰레기 주변을 가장 적게 지나온

경로 부터 지나가보면 된다.

pq에 쓰일 class의 compareTo 함수를 보면 된다.

 

이렇게 가다가 꽃을 만나면 가장 적은 쓰레기를 만나는게 보장이 된다.

 

출발지점과 꽃 지점은 쓰레기 주변으로 인식안한다는 것에 주의하자.

 

3. 자바 코드

package Gold;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class P1445일요일아침의데이트 {
	static class node implements Comparable<node>{
		int x;
		int y;
		int g;
		int b;
		public node(int x, int y, int g, int b) {
			this.x = x;
			this.y = y;
			this.g = g;
			this.b = b;
		}
		@Override
		public int compareTo(node o) {
			if(this.g == o.g) {
				return this.b - o.b;
			}
			
			return this.g - o.g;
		}
		
	}
	
	static char map[][];
	static boolean visited[][];
	static int N,M;
	static node start;
	static List<Point> gg;
	static int dr[] = {1,-1,0,0};
	static int dc[] = {0,0,1,-1};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new char[N][M];
		visited = new boolean[N][M];
		
		gg = new ArrayList<Point>(); 
		for(int i = 0 ; i < N ; i++) {
			String S = br.readLine();
			for(int j = 0 ; j < M ; j++) {
				map[i][j] = S.charAt(j);
				if(map[i][j] == 'S')
					start = new node(i,j,0,0);
				if(map[i][j] == 'g') 
					gg.add(new Point(i,j));
			}
		}
		make_b();
		PriorityQueue<node> gogo = new PriorityQueue<node>();
		gogo.add(start);
		visited[start.x][start.y] = true;
		int resultg = 0;
		int resultb = 0;
		gg:while(!gogo.isEmpty()) {
			node now = gogo.poll();
			for(int i = 0 ; i < 4 ; i++) {
				int row = now.x + dr[i];
				int col = now.y + dc[i];
				int g = now.g;
				int b = now.b;
				if(row<0 || col <0 || row>= N || col >= M)
					continue;
				if(visited[row][col])
					continue;
				if(map[row][col] == 'F') {
					resultg = g;
					resultb = b;
					break gg;
				}
				if(map[row][col] == 'g')
					g++;
				if(map[row][col] == 'b')
					b++;
				visited[row][col] = true;
				gogo.offer(new node(row, col, g, b));
			}
			
		}
		System.out.println(resultg+" "+resultb);
		
	}
	static void make_b() {
		for(int i = 0 ; i < gg.size() ; i++) {
			Point now = gg.get(i);
			for(int d = 0 ; d< 4 ; d++) {
				int row = now.x + dr[d];
				int col = now.y + dc[d];
				if(row<0 || col <0 || row>= N || col >= M)
					continue;
				if(map[row][col] == '.' )
					map[row][col] = 'b';
			}
		}
	}
	

}

4. 마치며

이전에 비슷한 문제를 풀어본 것 같아

빠르게 해결할 수 있었다.