백준 6087 <레이저 통신>

우선순위 큐를 사용해봤다면 생각보다 어렵지 않았던 문제 

 

우선순위 큐를 사용하여 거울을 작게 설치한 것부터 큐에서 꺼낼 수 있도록 한다!

 

문제 주의사항!

 

    90도로 회전하거나 직선으로 가는 총 3가지 경우만 생각해준다.--> 즉 뒤로 반사되는 경우는 없음!

 

 

문제 해결 순서

1. 시작점을 정해서 우선순위 큐에 넣어준다.
2. 90도로 회전하게 되면 count를 1 증가시켜주고 직선으로 가게 되면 증가시켜주지 않는다.
3. 큐에서 꺼낸 점이 종료점이면 result에 count값을 넣고 return 한다

 

현재의 좌표와 거울을 세운 갯수와 이전의 방향을 나타내기 위한 변수를 who라는 클래스에 선언!

 

BFS를 돌면서 90도로 회전하게 되면 count를 1 증가시켜주고 직선으로 가게 되면 증가 X

 

이 부분에서 특이한 점이 있다면 

중요!! 우선 순위에 큐에 넣을 때 방문처리를 하지 않고 뺄 때 한 이유!!

 

                     

즉!! 이동할 지점이 같은 방향 이어 count가 작음에도 불구하고 visit 처리되어 그 방향으로 이동이 불가능하다!

전체 코드

 

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 who implements Comparable<who>{
		int x;
		int y;
		int d;
		int count;
		public who(int x, int y, int d, int count) {
			super();
			this.x = x;
			this.y = y;
			this.d = d;
			this.count = count;
		}
		@Override
		public int compareTo(who o) {
			// TODO Auto-generated method stub
			return this.count-o.count;
		}
	}
	
	static String map[];
	static boolean visit[][][];
	static int n,m,dir[][]= {{-1,0},{0,1},{1,0},{0,-1}},result,sx=-1,sy=-1,fx=-1,fy=-1;
	static PriorityQueue<who> pr=new PriorityQueue<who>();
	public static void main(String[] args) throws IOException {
		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 String[n];
		visit=new boolean[n][m][4];
		for(int i=0;i<n;i++) {
			map[i]=br.readLine();
			for(int j=0;j<m;j++) {
				if(map[i].charAt(j)=='C') {
					if(sx==-1&&sy==-1) {
						sx=i;
						sy=j;
					}else {
						fx=i;
						fy=j;
					}
				}
			}
		}
		bfs();
		System.out.println(result);
	}
	private static void bfs() {
		// TODO Auto-generated method stub
		pr.add(new who(sx,sy,0,0));
		pr.add(new who(sx,sy,1,0));
		pr.add(new who(sx,sy,2,0));
		pr.add(new who(sx,sy,3,0));
		while(!pr.isEmpty()) {
			who next=pr.remove();
			if(next.x==fx&&next.y==fy) {
				result=next.count;
				return;
			}
			if(visit[next.x][next.y][next.d])
				continue;
			visit[next.x][next.y][next.d]=true;
			for(int i=3;i<=5;i++) {
				int d=(next.d+i)%4;
				int x1=next.x+dir[d][0];
				int y1=next.y+dir[d][1];
				if(x1<0||x1>=n||y1<0||y1>=m||visit[x1][y1][d]||map[x1].charAt(y1)=='*')
					continue;
				if(d==next.d) {
					pr.add(new who(x1,y1,d,next.count));
				}
				else {
					pr.add(new who(x1,y1,d,next.count+1));
				}
			}
		}
	}
}