[Java] 프로그래머스. Study 3주차(BFS, DFS)

1. 타겟 넘버

https://school.programmers.co.kr/learn/courses/30/lessons/43165

코드

class Solution {
    int[] numbers;
    int target;
    int answer;
    
    void DFS(int index, int sum) {
        if(index == numbers.length) {
            if(sum == target) answer++;
            return;
        }
        DFS(index+1, sum+numbers[index]);
        DFS(index+1, sum-numbers[index]);
    }
    
    public int solution(int[] numbers, int target) {
        this.answer = 0;
        this.numbers = numbers;
        this.target = target;
        
        DFS(0,0);
        return answer;
    }
}

2. 네트워크

https://school.programmers.co.kr/learn/courses/30/lessons/43162

코드(DFS)

class Solution {
    int n;
    int[][] computers;
    int answer;
    boolean visited[];
    
    void dfs(int start) {
        visited[start] = true;
        for(int i=0; i< computers.length; i++) {
            if(!visited[i]&&computers[start][i]==1) {
                dfs(i);
            }
        }
    }
    
    public int solution(int n, int[][] computers) {
        this.n = n;
        this.computers = computers;
        this.visited = new boolean[computers.length];
        this.answer = 0;
        
        for(int i=0 ;i<computers.length; i++) {
            if(!visited[i]) {
                dfs(i);
                answer++;
            }
        }
        return answer;
    }
}

코드(BFS)

import java.util.*;
class Solution {
    int n;
    int[][] computers;
    int answer;
    boolean visited[];
    
    void bfs(int start) {
        visited[start] = true;
        Queue<Integer> qu = new LinkedList<>();
        qu.add(start);
        while(!qu.isEmpty()) {
            start = qu.poll();
            for(int i=0; i< computers.length; i++) {
                if(!visited[i] && computers[start][i]==1) {
                    visited[i] = true;
                    qu.add(i);
                }
            }
        }
    }
    
    public int solution(int n, int[][] computers) {
        this.n = n;
        this.computers = computers;
        this.visited = new boolean[computers.length];
        this.answer = 0;
        
        for(int i=0 ;i<computers.length; i++) {
            if(!visited[i]) {
                bfs(i);
                answer++;
            }
        }
        return answer;
    }
}

3. 게임 맵 최단거리

https://school.programmers.co.kr/learn/courses/30/lessons/1844

풀이

최단거리를 구하는 문제라서 DFS 대신 BFS로 구현

int[][] visited: 각 좌표에 대한 이동거리

 

캐릭터가 움직일 수 있는 상, 하, 좌, 우를 탐색해서 값이 1이면서 방문한 적이 없는 좌표는 큐에 담아준다.

큐에서 값을 빼고 해당 위치에서 다시 탐색을 한다.

반복문이 종료되었을 때 도착지점이 0이라면 길이 없는 것으로 판단, 즉 -1을 return한다.

좌) 예시 좌표 ,우) BFS 탐색 후 저장된 거리

코드

import java.util.*;
class Solution {
    public int solution(int[][] maps) {
        int answer = 0;
        int n = maps.length;
        int m = maps[0].length;
        Queue<int[]> qu = new LinkedList<>();
        int[][] visited = new int[n][m];
        
        int[] xPoint = {0, -1, 0, 1};
        int[] yPoint = {1, 0, -1, 0};

        qu.add(new int[]{0, 0});
        visited[0][0] = 1;
        while(!qu.isEmpty()) {
            int[] start = qu.poll();
            int x = start[0];
            int y = start[1];
            for(int i=0; i<4; i++) {
                int dx = x+xPoint[i];
                int dy = y+yPoint[i];
                if(dx>=0&&dy>=0&&dx<n&&dy<m) {
                    if(visited[dx][dy]==0&&maps[dx][dy]==1) {
                        visited[dx][dy] = visited[x][y]+1;
                        qu.add(new int[]{dx, dy});
                    }
                }
            }
        }
        return visited[n-1][m-1]==0 ? -1 : visited[n-1][m-1];
    }
}

4. 단어 변환

https://school.programmers.co.kr/learn/courses/30/lessons/43163

코드(DFS)

class Solution {
    String[] words;
    String target;
    int answer;
    boolean[] visited;
    
    public int solution(String begin, String target, String[] words) {
        this.words = words;
        this.target = target;
        answer = 0;
        visited = new boolean[words.length];
        DFS(begin, 0);
        
        return answer;
    }
    
    void DFS(String begin, int count) {
        if(begin.equals(target)) {
            answer = count;
            return;
        }
        
        for(int k=0; k<words.length; k++) {
            int len = 0;
            if(!visited[k]) {
                for(int i=0; i<words[k].length(); i++) {
                    if(begin.charAt(i)==words[k].charAt(i)) len++;
                }
                if(len == begin.length()-1) {
                    visited[k] = true;
                    DFS(words[k], count+1);
                    visited[k] = false;
                }
            }
            
        }
    }
}

5. 아이템 줍기

https://school.programmers.co.kr/learn/courses/30/lessons/87694

풀이

우선 사각형을 1로 채워서 테두리만 구분해주면 되겠구나 하고 그림을 그려봤다.

근데 문제에서 사각형은 점에서 점으로 이어져 있는데 좌표는 한칸이 점과 같은 역할을 하기 때문에 테두리가 구분이 되지 않는다는 문제점이 있었다.

따라서 모든 좌표를 2배씩 하면 위 사진처럼 한 칸 한 칸이 테두리가 된다.

1. 테두리를 포함한 사각형 내부의 좌표를 1로 채워준다.
2. 테두리를 제외한 사각형 내부의 좌표를 2로 채워주면 사각형의 테두리만 1의 값으로 남게 된다.
3. BFS로 각 좌표까지의 거리를 계산하고 아이템 좌표에 도착했을 때의 해당 좌표 거리값/2를 return 해준다.

코드

import java.util.*;
class Solution {
    int[][] newRectangle;
    int characterX;
    int characterY;
    int itemX;
    int itemY;
    int[][] dis;
    boolean[][] visited;
    
    int bfs() {
        Queue<int[]> qu = new LinkedList<>();
        int[] xPoint = {0, -1, 0, 1};
        int[] yPoint = {1, 0, -1, 0};
        qu.add(new int[]{characterX, characterY});
        dis[characterX][characterY] = 1;
        visited[characterX][characterY] = true;

        while(!qu.isEmpty()) {
            int[] start = qu.poll();
            if(start[0]==itemX&&start[1]==itemY) break;

            for(int i=0; i<4; i++) {
                int newX = start[0]+xPoint[i];
                int newY = start[1]+yPoint[i];

                if(newX>=0&&newY>=0&&newX<=102&&newY<=102) {
                    if(!visited[newX][newY]&&newRectangle[newX][newY]==1) {
                        qu.add(new int[]{newX, newY});
                        visited[newX][newY] = true;
                        dis[newX][newY] = dis[start[0]][start[1]] + 1;
                    }
                }
            }
        }

        return dis[itemX][itemY]/2;
    }
    
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        this.characterX = characterX*2;
        this.characterY = characterY*2;
        this.itemX = itemX*2;
        this.itemY = itemY*2;
        
        newRectangle = new int[102][102];
        dis = new int[102][102];
        visited = new boolean[102][102];

        //테두리를 포함한 모든 좌표값 1 넣기
        for(int[] arr : rectangle) {
            int x1 = arr[0]*2;
            int y1 = arr[1]*2;
            int x2 = arr[2]*2;
            int y2 = arr[3]*2;
            for(int k=x1; k<=x2; k++) {
                for(int i=y1; i<=y2; i++) {
                    newRectangle[k][i] = 1;
                }
            }
        }

        //테두리를 제외한 내부 좌표값 2 넣기
        for(int[] arr : rectangle) {
            int x1 = arr[0]*2;
            int y1 = arr[1]*2;
            int x2 = arr[2]*2;
            int y2 = arr[3]*2;
            for(int k=x1+1; k<x2; k++) {
                for(int i=y1+1; i<y2; i++) {
                    newRectangle[k][i] = 2;
                }
            }
        }

        return bfs();
    }
}

6. 여행 경로

https://school.programmers.co.kr/learn/courses/30/lessons/43164

풀이

핵심은 도착지를 기준으로 오름차순 정렬을 하고 DFS 탐색을 시작하는 것이다.

정렬을 하고 나서 탐색을 하면 가장 먼저 찾아지는 경로가 정답이기 때문에 dfs 메서드의 종료 조건에 answer[0]==null 을 추가했다.

1. 티켓의 출발지가 이전 여행지의 도착지면서 방문한 적이 없는 곳을 찾는다.
2. String[] result에 경로를 저장한다.
3. 만약 count가 티켓의 길이와 같다면 더 이상 여행지가 없는 것으로 간주하고 재귀를 종료한다.

코드

import java.util.*;
class Solution {
    String[][] tickets;
    boolean[] visited;
    String[] answer;
    
    void dfs(String start, int count, String[] result) {
        if(count== tickets.length&&answer[0]==null) {
            answer = result;
            return;
        }

        for(int i=0; i< tickets.length; i++) {
            if(tickets[i][0].equals(start)&&!visited[i]) {
                visited[i] = true;
                String[] str = Arrays.copyOfRange(result, 0, result.length+1);
                str[str.length-1] = tickets[i][1];
                dfs(tickets[i][1], count+1, str);
                visited[i] = false;
            }
        }
    }
    
    public String[] solution(String[][] tickets) {
        this.tickets = tickets;
        this.visited = new boolean[tickets.length];
        this.answer = new String[tickets.length+1];

        Arrays.sort(tickets, new Comparator<String[]>() {
            @Override
            public int compare(String[] o1, String[] o2) {
                if(o1[0].toString().contentEquals(o2[0].toString()))
                    return o1[1].toString().compareTo(o2[1].toString());
                else
                    return o1[0].toString().compareTo(o2[0].toString());
            }
        });

        dfs("ICN", 0, new String[]{"ICN"});
        return answer;
    }
}

8. 합승 택시 요금

https://school.programmers.co.kr/learn/courses/30/lessons/72413

 

풀이

플로이드-와샬 알고리즘은 거쳐가는 정점을 기준으로 더 적은 비용을 선택하는 알고리즘이다.

구현은 굉장히 간단하지만 시간복잡도는 O(n^3)이라서 자주 사용되는 알고리즘은 아니다.

1. 배열을 전부 매우 높은 숫자(이 문제에서는 요금이 100000 이하, 정점이 200개 이하라서 넉넉하게 30000000으로 설정했다.)로 채워준다.
2. i→i는 0으로 채워준다.
3. 문제에서 주어진 대로 시작점에서 도착점까지를 해당 비용으로 채워준다.

3번까지 진행하면 아래와 같이 dist 배열이 채워진 상태가 된다.

지금부터 값을 최소비용으로 다시 채워줄 건데 현재 들어가 있는 값과 거쳐가서 도착했을 때의 값을 비교해서 더 작은 값으로 채워준다.

예를 들어 1→3의 비용은 41인데 1→5→3의 비용은 24+24=48이니까 원래의 값인 41로 유지되는 것이다.

이렇게 최소 비용으로 배열이 완성되었다면 answer 변수에 현재의 answer 값과 계산한 요금 중 최소비용을 넣어준다.

여기서 계산한 요금이란 1~n까지 합승했을 때를 의미한다.

1까지 합승한 경우 : s→1 + 1→a + 1→b, 2까지 합승한 경우 : s→2 + 2→a + 2→b …

코드(플로이드-와샬 알고리즘)

import java.util.*;
class Solution {
    int n;
    int s;
    int a;
    int b;
    int[][] fares;
    final int infinity = 30000000;
    int answer;
    
    void floyd(int[][] dist) {
        for(int k=1; k<n+1; k++){
            for(int i=1; i<n+1; i++){
                for(int j=1; j<n+1; j++){
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

        for(int i=1; i<=n; i++) {
            if(dist[s][i] != infinity && dist[i][a] != infinity && dist[i][b] != infinity){
                answer = Math.min(answer, dist[s][i] + dist[i][a] + dist[i][b]);
            }
        }
    }
    
    public int solution(int n, int s, int a, int b, int[][] fares) {
        this.n = n;
        this.s = s;
        this.a = a;
        this.b = b;
        this.fares = fares;
        this.answer = infinity;
        int[][] dist = new int[n+1][n+1];

        for(int i=0; i<=n; i++) {
            Arrays.fill(dist[i], infinity);
        }
        for(int i=0; i<=n; i++) {
            dist[i][i] = 0;
        }
        for(int i=0; i< fares.length; i++) {
            dist[fares[i][0]][fares[i][1]] = fares[i][2];
            dist[fares[i][1]][fares[i][0]] = fares[i][2];
        }

        floyd(dist);
        
        return answer;
    }
}