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

 

6087번: 레이저 통신

크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서

www.acmicpc.net

코드설명

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;
}
}

+ Recent posts