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; } }
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 1629 곱셈 - 수학(Math) + 분할정복(DivideAndConquer) + 재귀(Recursive) JAVA (0) | 2023.08.28 |
---|---|
[백준] 1149 RGB거리 - 동적계획법(DP, Dynamic Programming) JAVA (0) | 2023.08.27 |
[백준] 2933 미네랄 - BFS + 구현 JAVA (0) | 2023.08.26 |
[백준] 1655 가운데를 말해요 - 우선순위큐(PriorityQueue) + 아이디어 + 시간초과 JAVA (0) | 2023.08.25 |
[백준] 2671 잠수함식별 - 문자열 + 정규표현식 JAVA (0) | 2023.08.24 |