알고리즘 풀이 - 백준 6087(레이저 통신, 그래프(BFS))

 

관련글

 

그래프 관련 포스팅은 여기를 참조
DFS 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

레이저를 발사하여 두 위치를 연결 시키는 경우, 레이저가 거울을 만나면 90도 반사될 수 있을 때, 최소의 거울을 위치하여 연결하는 경우를 찾는 문제

 

 

2. 풀이

 

A → B 위치로 이동할 때, 꺾이는 부분이 최소가 되도록 연결하는 문제이다.

BFS를 통해 현재 위치에서 목표 위치로 이동 가능한 모든 경우를 체크하여 각 위치에 거울을 놓을 필요가 있는지를 체크하면 된다.
거울을 놓을 필요가 있는 경우는 방향 전환이 발생하는 경우이다.(어떤 방향이든 이전 노드를 탐색 시에 이동한 방향과 다르다면 방향 전환이 있는 것이다.)

그럼 180도로 전환하는 경우는? 그건 아래와 같이 해결한다.

 

4 방향으로 이동할 수 있으니, 다음 탐색 정점이 이전 탐색 정점 이후 어느 방향으로 이동하는 지를 체크하여, 90도 꺾이는 경우인지 아닌지를 설정하며 탐색하면 된다.

 

이 때, 모든 정점은 0회 ~ INF회까지 꺾여서 탐색이 가능하다.(INF는 무한)

그러면 중복으로 탐색하는 경우를 최대한 제외하기 위해서는 각 정점까지 도달했을 때, 방향이 바뀌는 횟수를 저장해 현재 탐색 시에 이전보다 더 적게 방향 전환이 있었던 경우에만 추가 탐색하여 문제를 해결할 수 있다.
(180도로 방향 전환하는 경우는 이전에 이미 방문이 완료된 경우를 다시 탐색하기 때문에 더 적은 방향 전환 횟수로 방문하는 것이 불가하다!)

 

주의할 점은 초기 위치에서는 어느 방향으로 가든 꺾이는 경우는 없다는 것이다. 아래의 코드를 통해 정답을 알아보자.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

import java.io.*;
import java.util.*;

public class Main{
    static int w, h;    // Map의 너비, 높이 값
    static char[][] map; // Map 정보
    static ArrayList<Integer> list;  // 연결할 C 정보들

    // 상하좌우의 이동경로
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, -1, 0, 1};
    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());

        map = new char[h][w];
        list = new ArrayList<>();

        for(int i=0; i < h; i++){
            String s = br.readLine();
            for(int j=0; j < w; j++){
                map[i][j] = s.charAt(j);

                // 연결할 부분들은 list에 별도 저장
                if(map[i][j] == 'C'){
                    list.add(i * w + j);
                }
            }
        }

        // BFS 탐색 후 결과 반영
        int ans = bfs();
        System.out.println(ans);
        br.close();
    }

    // BFS로 탐색 수행하는 메소드
    private static int bfs(){
        // BFS 로 탐색 시작할 위치를 지정(C 중 1개)
        Queue<Pos> q = new LinkedList<>();
        int start = list.get(0);  // 시작하는 'C'
        int end = list.get(1);    // 연결될 'C'
        q.offer(new Pos(start / w, start % w, 0, 4)); // 초기 시작 위치 저장

        int[][] visited = new int[h][w]; // 90도로 꺾여서 도달하는 경우 중 최소의 경우를 넣는다.
        for(int i=0; i < h; i++){
            Arrays.fill(visited[i], Integer.MAX_VALUE);
        }
        visited[start / w][start % w] = 0;

        // 반환할 값
        int ans = Integer.MAX_VALUE;
        while(!q.isEmpty()){
            Pos p = q.poll();
            int y = p.y;
            int x = p.x;

            if(y == end / w && x == end % w){
                ans = Math.min(ans, p.curve);
            }

            for(int i=0; i < 4; i++){
                int ny = y + dy[i];
                int nx = x + dx[i];

                if(ny < 0 || ny >= h || nx < 0 || nx >= w || visited[ny][nx] < p.curve) continue;
                if(map[ny][nx] != '*'){
                    // 방향이 다르다면 꺾이는 것
                    // p.dir이 4라면 초기 위치라는 뜻이며, 이 때는 어느 방향으로 가든 꺾이지 않는다.
                    int curve = p.dir == 4 || p.dir == i ? p.curve : p.curve+1;
                    
                    // 이전 방문 시보다 꺾이는 횟수가 적게 도달한 경우
                    if(visited[ny][nx] >= curve){
                        visited[ny][nx] = curve;
                        q.offer(new Pos(ny, nx, curve, i));
                    }

                }
            }
        }
        return ans;
    }
}

class Pos{
    int y;
    int x;
    int curve;
    int dir;

    public Pos(int y, int x, int curve, int dir){
        this.y=y;
        this.x=x;
        this.curve=curve;
        this.dir=dir;
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.