[ Baekjoon - 10/22 ] - 6087번: 레이저 통신

• 문제 링크 : https://www.acmicpc.net/problem/6087

6087번: 레이저 통신

 

• 소요 시간 : 2시간 반

 

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 1초
     • 메모리 : 128MB
   • 문제
     
     • W x H의 지도(1≤W,H≤100)
     • 지도에 출발점 및 도착점(C), 벽(*), 빈방(.)이 있을때 C를 연결하기위한 최소 거울의 수를 출력하는 문제
     • 거울은 /과 \모양이 있으며, 90도씩 방향을 회전 시킬 수 있다.
   • 이해
     • 문제이해는 어렵지 않았고, 완탐을 통해 전체 탐색하거나, 규칙을 찾아야하는 문제라고 생각했다.
2. 문제를 익숙한 용어로 재정의와 추상화

   • 

   • 두 거울 형태에 따라, 상 하 좌 우 에서 레이저가 들어왔을때 어떻게 반사되는지 그려보았고, 수평방향만 아닌 방향으로 갈 수 있다는 것을 알게되었다.
   • 맵을 그려보며 어떻게 해결해야할지 분석해 보았다.
3. 문제를 어떻게 해결할 것인가
   • 1st 접근 - 완탐)

     • 

     • C에서부터 직진으로 상, 하, 좌, 우 방향으로는 방향의 변화가 없으므로 값을 그대로하고, 대각선 방향으로는 한번 꺾어야 하므로 원래 값에 +1을 한 값을 넣는 방식으로 가야한다고 생각했다.
     • 즉 아래의 그림처럼 각 칸에 가려면 몇번 꺾어야하는지가 나타나게 될것이다.

     • 

     • 이렇게 나타낸다면 출발점 C가 아닌 도착점 C에 갔을때 몇개의 거울을 설치해야 갈 수 있는지 알 수 있다.
4. 위 계획을 검증
   • 규칙을 찾기위해 케이스별로 나눠 따져본 것이므로 이미 검증이라 볼 수 있다. 
5. 계획 수행 (실제코드 작성)
   1. Java 11

      • import java.io.*;
        import java.util.*;
        
        public class Main {
            static int W,H;
            static List<Integer> point;
            static char[][] map;
            static int[][] changeDirectionCnt;
            static int[] dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
        
            public static void main(String[] args) throws IOException {
                //System.setIn(new FileInputStream("src/input.txt"));
        
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                StringTokenizer st = new StringTokenizer(br.readLine());
        
                W = Integer.parseInt(st.nextToken());
                H = Integer.parseInt(st.nextToken());
        
                point = new ArrayList<>();
        
                map = new char[H][W];
                changeDirectionCnt = new int[H][W];
                for (int h=0; h<H; h++) {
                    String temp = br.readLine();
                    for (int w=0; w<W; w++) {
                        map[h][w] = temp.charAt(w);
                        // 모든 좌표에 -2 넣기
                        changeDirectionCnt[h][w] = -2;
                        // 도착지거나 출발지라면, 한 곳에 -1 넣기
                        if (map[h][w] == 'C') {
                            point.add(h);
                            point.add(w);
                            if(point.size()==4){
                                map[h][w] = '.';
                            }
                        }
                    }
                }
                bfs();
                System.out.println(changeDirectionCnt[point.get(2)][point.get(3)]);
            }
        
            public static void bfs() {
                Queue<int[]> queue = new LinkedList<>();
                // 시작점(C중 하나) 넣기
                queue.offer(new int[] {point.get(0), point.get(1)});
                changeDirectionCnt[point.get(0)][point.get(1)] = -1;
        
                while (!queue.isEmpty()) {
                    //1. 큐에서 꺼내옴
                    int[] q = queue.poll();
                    int x = q[0], y = q[1];
                    //2. 목적지인가 - 나머지 C인가
                    if (x==point.get(2) && y==point.get(3)) {
                        return;
                    }
                    // 사방으로 3번조건에 부합하지 않을때까지 나아감
                    for (int i=0; i<4; i++) {
                        int nx = x + dx[i];
                        int ny = y + dy[i];
                        //3. 연결되어있는가 - 맵안, 벽이 아닌곳이면 가능
                        while (0<=nx && nx<H && 0<=ny && ny<W && map[nx][ny]=='.') {
                            //4. 갈수 있는가 - 아직 방향이 한번도 갱신된적 없으면 가능
                            if (changeDirectionCnt[nx][ny] == -2) {
                                //5. 큐에 넣음
                                queue.add(new int[] {nx, ny});
                                //6. 체크인
                                changeDirectionCnt[nx][ny] = changeDirectionCnt[x][y] + 1;
                            }
                            nx += dx[i];
                            ny += dy[i];
                        }
                    }
                }
            }
        }

   2. Python 3

      • import sys
        from collections import deque
        
        input = sys.stdin.readline
        
        W, H = map(int, input().split())
        point = []
        
        dx = [0, 0, 1, -1]
        dy = [1, -1, 0, 0]
        board = []
        
        #  모든 좌표에 -2 넣기
        changeDirectionCnt = [[-2 for _ in range(W)] for _ in range(H)]
        for h in range(H):
            temp = list(input().rstrip())
            board.append(temp)
            for w in range(W):
                #  도착지거나 출발지라면, 한 곳에 -1 넣기
                if board[h][w] == 'C':
                    point.append(h)
                    point.append(w)
                    if len(point) == 4:
                        board[h][w] = '.'
        
        def BFS():
            queue = deque()
            queue.append((point[0], point[1]))
            changeDirectionCnt[point[0]][point[1]] = -1
        
            while queue:
                # 1. 큐에서 꺼내옴
                q = queue.popleft()
                x = q[0]
                y = q[1]
                # 2. 목적지인가 - 나머지 C인가
                if x == point[2] and y == point[3]:
                    return
                # 사방으로 3번조건에 부합하지 않을때까지 나아감
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    # 3. 연결되어있는가 - 맵안, 벽이 아닌곳이면 가능
                    while 0 <= nx < H and 0 <= ny < W and board[nx][ny] == '.':
                        # 4. 갈수 있는가 - 아직 방향이 한번도 갱신된적 없으면 가능
                        if changeDirectionCnt[nx][ny] == -2:
                            # 5. 큐에 넣음
                            queue.append((nx, ny))
                            # 6. 체크인
                            changeDirectionCnt[nx][ny] = changeDirectionCnt[x][y] + 1
                        nx += dx[i]
                        ny += dy[i]
        
        BFS()
        print(changeDirectionCnt[point[2]][point[3]])

 

 

• 결과