백준 1445 <일요일 아침의 데이트>

골드 2의 문제 하지만 골드 2보다는 쉬운 난이도라고 생각한다.

 

이 문제에서 헷갈렸던 점은 언제 인접한 칸을 체크해주냐는 것이었다.

 

이렇게 밑줄 친 부분을 보면 이동 할 칸에 쓰레기가 있다면 옆을 살피지 않고 없다면 4방을 탐색해서 체크를 해주는 것이었다. 이 부분만 고려해 우선순위 큐를 사용해주면 쉽게 해결되는 문제이다.

 

문제 풀이

1. 쓰레기를 가장 적게 밟은 것 중에 적게 옆을 지나간 횟수의 위치를 꺼내 준다.
2. 4방향 탐색 후 이동할 칸에 쓰레기가 존재한다면 쓰레기 카운터를 증가시키고 그렇지 않다면 4방향을 탐색해 쓰레기가 있는지 확인해서 있다면 옆에 쓰레기 있는 카운터를 증가시킨 후 큐에 넣는다.
3. 이렇게 꽃이 있을 때까지 진행하는 것이다.

우선순위 큐로 비교해주기 위한 class를 하나 생성해주었다.

다음 위치로 이동후 쓰레기가 있는 경우 없는 경우를 판단한 것이다.

 

이렇게 생각만 할 수 있다면 쉽게 구현할 수 있는 문제이다. 

 

전체 코드

package solution;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	
	public static class now implements Comparable<now>{
		int x;
		int y;
		int count;
		int nex;
		public now(int x, int y, int count, int nex) {
			super();
			this.x = x;
			this.y = y;
			this.count = count;
			this.nex = nex;
		}
		@Override
		public int compareTo(now o) {
			// TODO Auto-generated method stub
			if(this.count>o.count) {
				return 1;
			}
			else if(this.count==o.count) {
				return this.nex-o.nex;
			}
			return -1;
		}
		
	}
	static int n,m,sx,sy,fx,fy,resulta,resultb;
	static PriorityQueue<now> pq;
	static String map[];
	static boolean visit[][];
	static int dir[][]= {{-1,0},{0,1},{1,0},{0,-1}};
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		pq=new PriorityQueue<now>();
		n=Integer.parseInt(st.nextToken());
		m=Integer.parseInt(st.nextToken());
		map=new String[n];
		visit=new boolean[n][m];
		for(int i=0;i<n;i++) {
			map[i]=br.readLine();
			for(int j=0;j<m;j++) {
				if(map[i].charAt(j)=='F') {
					fx=i;
					fy=j;
				}
				else if(map[i].charAt(j)=='S') {
					sx=i;
					sy=j;
				}
			}
		}
		pq.add(new now(sx,sy,0,0));
		bfs();
		System.out.println(resulta+" "+resultb);

	}
	private static void bfs() {
		// TODO Auto-generated method stub
		while(!pq.isEmpty()) {
			now next=pq.remove();
			if(visit[next.x][next.y]) {
				continue;
			}
			visit[next.x][next.y]=true;
			for(int i=0;i<4;i++) {
				int x1=next.x+dir[i][0];
				int y1=next.y+dir[i][1];
				if(x1<0||x1>=n||y1<0||y1>=m||visit[x1][y1]) {
					continue;
				}
				if(x1==fx&&y1==fy) {
					resulta=next.count;
					resultb=next.nex;
					return;
				}
				if(map[x1].charAt(y1)=='g') {
					pq.add(new now(x1,y1,next.count+1,next.nex));
				}
				else {
					boolean flag=true;
					for(int j=0;j<4;j++) {
						int x2=x1+dir[j][0];
						int y2=y1+dir[j][1];
						if(x2<0||x2>=n||y2<0||y2>=m) {
							continue;
						}
						if(map[x2].charAt(y2)=='g') {
							pq.add(new now(x1,y1,next.count,next.nex+1));
							flag=false;
							break;
						}
					}
					if(flag)
						pq.add(new now(x1,y1,next.count,next.nex));
				}
			}
		}
	}


}