[백준] 6087 레이저 통신 - BFS JAVA

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

6087번: 레이저 통신

코드설명

BFS를 활용하는 문제입니다.

 

문제에서 신경써야할점은, 거울에서 레이저가 튕긴다면 90도 회전한다는 것입니다. 

만약 오른쪽이나 왼쪽에서 레이저가 발사되서 들어온다면, 상, 하 로 밖에 레이저가 이동하지 못한다는 의미입니다.

 

이를 위해서 visited[H][W][2] 를 선언하여

visited[H][W[0] : 가로로 들어왔을때의 방문배열,

visited[H][W][1] : 세로로 들어왔을때의 방문배열

이렇게 2가지를 선언하여 BFS를 진행하면 최적의 거리를 찾을 수 있습니다.

 

 

관련 테스트코드로는,

7 8
.......
......C
......*
.......
.......
.......
*C.....
.......

answer
1



7 8
.......
......C
......*
.......
.......
..*****
*C.....
.......


answer
1

입니다.

2번쨰 테스트케이스를 통과하면, visited[][][2]로 처리하는 이유를 알 수 있습니다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.regex.Pattern;

public class Main {
	public static int W, H;
	public static char[][] map;
	
	//상하좌우
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static int answer = 0;
	
	public static boolean[][][] visited;
	public static Node firstC = null;
	public static Node secondC= null;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	W = Integer.parseInt(st.nextToken());
    	H = Integer.parseInt(st.nextToken());
    	visited = new boolean[H][W][2];
    	map = new char[H][W];
    	for(int i=0;i<H;i++) {
    		String str = br.readLine();
    		for(int j=0;j<W;j++) {
    			map[i][j] = str.charAt(j);
    			if(map[i][j] == 'C' && firstC == null) {
    				firstC = new Node(i, j, false, 0); //처음에는 4가지 방향 다 가야하므로 상관없습니다.
    			}else if(map[i][j] =='C' && firstC != null) {
    				secondC = new Node(i, j, false, 0); 
    			}
    		}
    	}
    	BFS();
    }
    
    //bfs의 방식을 벽이 다을때까지 진행하면될것입니다.
    public static void BFS() {
    	visited = new boolean[H][W][2];
    	Queue<Node> q = new LinkedList<>();
    	q.add(new Node(firstC.r, firstC.c, true, 0)); //먼저 가로로 가는경우 
    	q.add(new Node(firstC.r, firstC.c, false, 0)); //세로로 가야하는 경우
    	
    	visited[firstC.r][firstC.c][0] = true;
    	visited[firstC.r][firstC.c][1] = true;
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int r = temp.r;
    		int c = temp.c;
    		boolean horizontalFlag = temp.horizontalFlag;
    		int cnt = temp.cnt;
    		if( r == secondC.r && c == secondC.c) {
    			System.out.println(cnt-1);
    			System.exit(0);
    			return ;
    		}
    		
    		if(horizontalFlag == true ) { //가로로 레이저 발사
        		for(int dir=2;dir<4;dir++) {
        			int nr = r + dx[dir];
        			int nc = c + dy[dir];
        			boolean nHorizontalFlag = !horizontalFlag; //온방향의 90%도로 꺽어줍니다.
        			int nCnt = cnt + 1;
            		while(true) { //각 방향에서 *를 만날떄까지 끝까지 갑니다.
            			if(nr < 0 || nr >= H || nc < 0 || nc >= W) break; //범위 벗어날시 나갑니다.
            			if(map[nr][nc] == '*') break;
            			if(visited[nr][nc][0] == true) break;
            			visited[nr][nc][0] = true;
            			q.offer(new Node(nr, nc, nHorizontalFlag, nCnt));
            			nr += dx[dir];
            			nc += dy[dir];
            		}
        		}    			
    		}
    		else if(horizontalFlag == false) {
        		for(int dir=0;dir<2;dir++) {
        			int nr = r + dx[dir];
        			int nc = c + dy[dir];
        			boolean nHorizontalFlag = !horizontalFlag; //온방향의 90%도로 꺽어줍니다.
        			int nCnt = cnt + 1;
            		while(true) { //각 방향에서 *를 만날떄까지 끝까지 갑니다.
            			if(nr < 0 || nr >= H || nc < 0 || nc >= W) break; //범위 벗어날시 나갑니다.
            			if(map[nr][nc] == '*') break;
            			if(visited[nr][nc][1] == true) break;
            			visited[nr][nc][1] = true;
            			q.offer(new Node(nr, nc, nHorizontalFlag, nCnt));
            			nr += dx[dir];
            			nc += dy[dir];
            		}
        		}    			
    		}
    		

    	}

    }
    
}

class Node{
	int r;
	int c;
	boolean horizontalFlag; //가로로 가야할 차례인가 처리합니다.
	int cnt=0;
	public Node(int r, int c, boolean horizontalFlag, int cnt) {
		this.r=r;
		this.c=c;
		this.horizontalFlag = horizontalFlag;
		this.cnt = cnt;
	}
}