백준 6087번 레이저 통신

문제

나의 풀이

import java.util.*;

public class Main {
    static class Pair {
        int first, second;
        Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }
    
    static final int dx[] = { 0, 0, 1, -1 };
    static final int dy[] = { 1, -1, 0, 0 };
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        String a[] = new String[n];
        int sx, sy, ex, ey;
        sx = sy = ex = ey = -1;
        for(int i = 0; i < n; i++) {
            a[i] = sc.next();
            for(int j = 0; j < m; j++) {
                if(a[i].charAt(j) == 'C') {
                    if(sx == -1) {
                        sx = i;
                        sy = j;
                    } else {
                        ex = i;
                        ey = j;
                    }
                }
            }
        }
        
        int d[][] = new int[n][m];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                d[i][j] = -1;
            }
        }
        
        Queue<Pair> q = new LinkedList<Pair>();
        q.add(new Pair(sx, sy)); // 시작점
        d[sx][sy] = 0;
        
        while(!q.isEmpty()) {
            Pair p = q.poll();
            int x = p.first;
            int y = p.second;
            for(int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                while(0 <= nx && nx < n && 0 <= ny && ny < m) { // 범위 내에서 반복
                    if(a[nx].charAt(ny) == '*') { // 벽인 경우
                        break;
                    }
                    if(d[nx][ny] == -1) { // 아직 방문하지 않은 경우
                        d[nx][ny] = d[x][y] + 1; 
                        q.add(new Pair(nx, ny));
                    }
                    // 네방향에 있는 모든 점 탐방
                    nx += dx[k];
                    ny += dy[k];
                }
            }
        }
        
        System.out.println(d[ex][ey] - 1); 
    }
}

거울을 설치한다는 것은 직선의 방향을 바꾸는 것이라고 볼 수 있다. 거울의 개수는 두 C를 연결하는 데 필요한 직선의 최소 개수에서 -1을 한 것이라고 볼 수 있다. BFS에서 다음 정점을 인접한 네 방향에 있는 점만 넣는 것이 아니고 네 방향에 있는 모든 점을 넣는 방식으로 바꿔서 해결하면 된다.

결과

백준 1963번 소수 경로

문제

나의 풀이

import java.util.*;

public class Main {
    public static int change(int num, int index, int digit) { // index번째 수를 digit으로 바꾸기
        if(index == 0 && digit == 0) {
            return -1;
        }
        String s = Integer.toString(num);
        StringBuilder sb = new StringBuilder(s);
        sb.setCharAt(index, (char)(digit + '0')); // 바꾸기
        return Integer.parseInt(sb.toString());
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        boolean prime[] = new boolean[10001];
        for(int i = 2; i <= 10000; i++) { // 에라토스테네스의 체
            if(prime[i] == false) {
                for(int j = i * i; j <= 10000; j+= i) {
                    prime[j] = true;
                }
            }
        }
        for(int i = 0; i <= 10000; i++) {
            prime[i] = !prime[i];
        }
        
        int t = sc.nextInt();
        while(t-- > 0) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            boolean c[] = new boolean[10001];
            int d[] = new int[10001];
            
            Queue<Integer> q = new LinkedList<Integer>();
            d[n] = 0; // 시작점
            c[n] = true;
            q.add(n);
            
            while(!q.isEmpty()) {
                int now = q.poll();
                for(int i = 0; i < 4; i++) { // 네 자리
                    for(int j = 0; j <= 9; j++) { // 수의 범위 0~9
                        int next = change(now, i, j);
                        if(next != -1) { // 바꿀 수 있는 경우
                            if(prime[next] && c[next] == false) { // 소수면서 방문하지 않은 경우
                                q.add(next);
                                d[next] = d[now] + 1; // 횟수 업데이트
                                c[next] = true;
                            }
                        }
                    }
                }
            }
            
            System.out.println(d[m]);
        }
    }
}

맨 처음에 에라토스테네스의 체를 이용해서 소수 정보를 다 저장해 놓는다. 그런 다음 bfs 탐색을 통해 i번째 자리의 수를 j로 바꾸면서 바꾸는 게 가능한 경우 큐에 삽입해서 다음 단계로 넘어가는 형식으로 하면 된다.

결과

인프런 사다리 타기

문제

나의 풀이

public class ClimbTheLadder {
    static public char[] solution(int n, int[][] ladder) {
        char answer[] = new char[n];
        for(int i =0 ; i < n; i++) {
            answer[i] = (char)(i + 65);
        }
        for(int line[] : ladder) {
            for(int x : line) {
                char tmp = answer[x];
                answer[x] = answer[x - 1];
                answer[x - 1] = tmp;
            }
        }
        return answer;
    }
    public static void main(String[] args) {
        System.out.println(ClimbTheLadder.solution(5, new int[][]{{1, 3}, {2, 4}, {1, 4}}));
        System.out.println(ClimbTheLadder.solution(7, new int[][]{{1, 3, 5}, {1, 3,6}, {2, 4}}));
        System.out.println(ClimbTheLadder.solution(8, new int[][]{{1, 5}, {2, 4, 7}, {1, 5, 7}, {2, 5, 7}}));
    }
}

모든 가로줄에 대해서 배열의 순서를 바꿔주면 된다.

결과