[Java] 프로그래머스 컬러링북 & 프로그래머스 합승택시요금

매일 코테 문제를 풀고 있지만 블로그에는 오랜만에 코테 문제를 올려본다.

 

1. 프로그래머스 컬러링북(Lv.2)

 

단순 BFS 문제이다. 일반 BFS방식으로 풀면 쉽게 풀리는 문제이다.

다른 색이면 cnt++ 하고 bfs로 해당 색의 개수를 세서 max_cnt를 갱신해주는 방식으로 풀었다.

import java.util.*;
class Solution {
    static boolean[][] visited;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int max_cnt;
    public int[] solution(int m, int n, int[][] picture) {
        visited = new boolean[m][n];
        int cnt = 0;
        max_cnt = 0;
        for (int i =0 ; i < m; i++){
            for (int j = 0; j < n; j++){
                if (picture[i][j] != 0){
                    bfs(i, j, m, n, picture);
                    cnt++;
                }
            }
        }
        int[] answer = {cnt, max_cnt};
        return answer;
    }
    
    private static void bfs(int a, int b, int m, int n, int[][] picture){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {a,b});
        visited[a][b] = true;
        int num = picture[a][b];
        int num_cnt = 1;
        picture[a][b] = 0;
        
        while (!queue.isEmpty()){
            int[] now = queue.poll();
            int x = now[0];
            int y = now[1];
            for (int i = 0; i< 4; i++){
                int nx = dx[i] + x;
                int ny = dy[i] + y;
                if (nx < 0 || ny < 0 || nx > m-1 || ny > n-1) continue;
                if (visited[nx][ny]) continue;
                if (picture[nx][ny] == 0 || picture[nx][ny] != num) continue;
                visited[nx][ny] = true;
                picture[nx][ny] = 0; //방문했으면 picture에서 해당 칸을 0으로 만들기
                queue.offer(new int[] {nx,ny});
                num_cnt++;
                
            }
        }
        max_cnt = Math.max(max_cnt, num_cnt); // 다 돌았으면 max_cnt값 갱신
        
    }
}

 

 

 

2. 프로그래머스 합승택시요금(Lv.3)

 

다익스트라 문제이다.

해당 문제는 백준 1504 특정한 최단경로의 문제와 비슷하다.

필자도 1504문제풀이와 비슷하게 풀었더니 풀수 있었다.

노드는 양방향이기때문에 최단 거리도 a -> i  = i ->a 가 똑같다. 

따라서 s에서 출발한 최단 경로 , a에서 출발한 최단 경로, b에서 출발한 최단 경로를 구해주고서,

(s에서 출발하여 각 i번 노드까지 최단 거리) + (i번 노드에서 a까지의 최단 거리) + (i번 노드에서 b까지의 최단 거리) 의 최소합을 구해줬다.

import java.util.*;

class Solution {
    static ArrayList<Node>[] graph;
    
    public int solution(int n, int s, int a, int b, int[][] fares) {
        graph = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        
        for (int[] fare : fares) {
            int start = fare[0];
            int end = fare[1];
            int cost = fare[2];
            graph[start].add(new Node(end, cost));
            graph[end].add(new Node(start, cost));
        }
        
        int[] S = dijkstra(s, n); // s에서 출발
        int[] A = dijkstra(a, n); // a에서 출발
        int[] B = dijkstra(b, n); // b에서 출발

        int min = Integer.MAX_VALUE;

        for(int i=1; i<=n; i++) {
        // (s에서 i노드까지 거리) + (i노드에서 a까지의 거리) + (i노드에서 b까지의 거리) 의 최소를 구해준다.
            if(min > S[i] + A[i] + B[i]) { 
                min = S[i] + A[i] + B[i];
            }
        }

        return min;
    }
    
    public static int[] dijkstra(int start, int n) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        boolean[] visited = new boolean[n+1];
        int[] dist = new int[n+1];
        Arrays.fill(dist, Integer.MAX_VALUE); // 최대값으로 초기화
        dist[start] = 0;
        pq.add(new Node(start, 0));
        
        while (!pq.isEmpty()) {
            Node now = pq.poll();
            int idx = now.index;
            
            if (visited[idx]) continue;
            visited[idx] = true;
            
            for (Node next : graph[idx]) {
                int cost = dist[idx] + next.cost;
                if (dist[next.index] > cost) {
                    dist[next.index] = cost;
                    pq.offer(new Node(next.index, cost));
                }
            }
        }
        
        return dist;
    }
    
    public static class Node implements Comparable<Node> {
        int index;
        int cost;
        
        public Node(int index, int cost){
            this.index = index;
            this.cost = cost;
        }
        
        @Override
        public int compareTo(Node o){
            return Integer.compare(this.cost, o.cost);
        }
    }
}

 

 

 

궁금한점이 있다면 댓글 달아주세용^_^