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

📚 문제

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.
지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.
아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.

• 첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.

• 두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.

위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다. 만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

📝 문제 해결

BFS는 시작 지점에서 가까운 노드부터 차례대로 탐색하는 알고리즘으로 최단경로 문제를 풀 때 효과적이다.

1. (0, 0) 노드부터 큐에 삽입해주고

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 벽이 아니고 아직 방문하지 않은 노드가 있다면 삽입해주고 카운트 + 1을 해주고

3. 큐에 더이상 탐색할 노드가 없을 때까지 반복해주다가 상대방 진영에 도달했을 때 카운트값을 return해준다.

💻 코드

import java.util.*;

class Solution {
    public static int n, m;
    public static int answer = -1;
    
    public static int dx[] = {-1, 1, 0, 0};
    public static int dy[] = {0, 0, -1, 1};
    public static boolean visited[][];
    
    public int solution(int[][] maps) {
        n = maps.length;
        m = maps[0].length;
        visited = new boolean[n][m];
    
        return bfs(0, 0, maps);
    }
    
    public int bfs(int x, int y, int[][] maps){
        Queue<int[]> que = new LinkedList<>();
    
        que.add(new int[]{x, y, 1});
        visited[0][0] = true;

        while (!que.isEmpty()) {
            int temp[] = que.poll();
            x = temp[0];
            y = temp[1];
            int count = temp[2];
            
            if (x == n-1 && y == m-1) {
                answer = count;
                break;
            }

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

                if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if(maps[nx][ny] == 0) continue;
                if(!visited[nx][ny] && maps[nx][ny] == 1) {
                    visited[nx][ny] = true;
                    que.add(new int[]{nx, ny, count+1});
                }
            }
        }

        return answer;
    }
}

🔽 DFS 풀이

더보기

정확성은 통과하는데 효율성에서 탈락.. 좀 더 생각해봐야겠다..

import java.util.*;

class Solution {
    public static int n, m;
    public static int answer = Integer.MAX_VALUE;
    
    public static int dx[] = {-1, 1, 0, 0};
    public static int dy[] = {0, 0, -1, 1};
    public static boolean visited[][];
    public static int[][] count;
    
    public int solution(int[][] maps) {
        n = maps.length;
        m = maps[0].length;
        visited = new boolean[n][m];
        count = new int[n][m];
        
        visited[0][0] = true;
        count[0][0] = 1;
        
        dfs(0, 0, maps);
        
        return answer == Integer.MAX_VALUE ? -1 : answer;
    }
    
    public void dfs(int x, int y, int[][] maps){
        if(count[x][y] > answer) return;
        if(x == n-1 && y == m-1){
            answer = Math.min(answer, count[x][y]);
            return;
        }
        
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            
            if(maps[nx][ny] == 0) continue;
            
            if(!visited[nx][ny] && maps[nx][ny] == 1){
                visited[nx][ny] = true;
                count[nx][ny] = count[x][y] + 1;
                dfs(nx, ny, maps);
                visited[nx][ny] = false;
            }
        }
    }
}

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

📚 문제

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

 

제한 사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

 

입출력 예

n	computers	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

입출력 예 설명

예제 #1 아래와 같이 2개의 네트워크가 있습니다.

예제 #2 아래와 같이 1개의 네트워크가 있습니다.

 

📝 문제 해결

• DFS (깊이 우선 탐색)

시작 지점에 연결된 노드들 중 아직 방문하지 않은 노드들에 대해 반복적으로 메서드를 호출해 연결된 모든 노드를 탐색해주면 된다.

• BFS (너비 우선 탐색)

큐에 시작 지점을 넣어주고 연결된 노드들 중 아직 방문하지 않은 노드를 큐에 넣어주고 큐가 빌 때까지 반복해 준다.

💻 코드

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    static int[][] node;
    static boolean[] visited;
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        
        node = new int[n][n];
        visited = new boolean[n];
        
        for(int i=0; i<computers.length; i++){
            for(int j=0; j<n; j++){
                if(computers[i][j] == 1) node[i][j] = node[j][i] = 1;
            }
        }
        
        for(int i=0; i<n; i++){
            if(!visited[i]){
                //dfs(n, i);
                bfs(n, i);
                answer ++;
            }
        }
        return answer;
    }
    
    static void dfs(int n, int index){
        visited[index] = true;
        
        for(int i=0; i<n; i++){
            if(node[index][i] == 1 && !visited[i]) dfs(n, i);
        }
    }
    
    static void bfs(int n, int index){
        Queue<Integer> que = new LinkedList<Integer>();
        que.offer(index);
        visited[index] = true;
        
        while(!que.isEmpty()){
            int temp = que.poll();
            
            for(int i=0; i<n; i++){
                if(node[temp][i] == 1 && !visited[i]){
                    que.offer(i);
                    visited[i] = true;
                }
            }
        }
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/43163?language=java 

📚 문제

문제 설명

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

📝 문제 해결

• bfs (너비 우선 탐색법)

begin 단어를 큐에 넣어주고 words 단어 중 begin과 한 개의 알파벳만 다르고 아직 방문하지않은 단어를 큐에 넣어주고 count+1 해준 뒤 방문처리한다. 큐의 단어가 target과 같은 경우, count를 return해줌

• dfs (깊이 우선 탐색법)

words 단어 중 begin과 한 개의 알파벳만 다르고 아직 방문하지않은 단어를 방문처리해주고 count+1 후 재귀 호출해준다. (모든 경우의 수를 탐색하기 위해 visitd[i] = false로 되돌려줘야함)

넘겨준 begin값이 target과 같은 경우 answer를 최솟값으로 갱신해준다.

💻 코드

import java.util.Queue;
import java.util.LinkedList;

class Node{
    String word;
    int count;
    
    Node(String word, int count){
        this.word = word;
        this.count = count;
    }
}

class Solution {
    int answer = Integer.MAX_VALUE;
    boolean[] visited;
    
    public int solution(String begin, String target, String[] words) {
        visited = new boolean[words.length];
        
        return bfs(begin, target, words);
        
        /*
        dfs(begin, target, words, 0);
        if(answer == Integer.MAX_VALUE){
            return 0;
        }
        return answer;
        */
    }
    
    public int bfs(String begin, String target, String[] words){
        Queue<Node> que = new LinkedList<>();
        que.add(new Node(begin, 0));
        
        while(!que.isEmpty()){
            Node cur = que.poll();
            
            if(cur.word.equals(target)) return cur.count;
            
            for(int i=0; i<words.length; i++){
                int match = 0;
                for(int j=0; j<begin.length(); j++){
                    if(cur.word.charAt(j) == words[i].charAt(j)) match++;
                }
                
                if(!visited[i] && match == begin.length()-1){
                    que.add(new Node(words[i], cur.count+1));
                    visited[i] = true;
                }
            }
        }
        
        return 0;
    }
    
    public void dfs(String begin, String target, String[] words, int count){
        if(begin.equals(target)){
            answer = Math.min(answer, count);
            return;
        }
        
         for(int i=0; i<words.length; i++){
             if(visited[i])  continue;
                
             
             int match = 0;
             for(int j=0; j<begin.length(); j++){
                 if(begin.charAt(j) == words[i].charAt(j))  match++;
             }
             
             if(match == begin.length()-1){
                 visited[i] = true;
                 dfs(words[i], target, words, count+1);
                 visited[i] = false;
             }
         }
    }
}

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

📚 문제

문제 설명

 

입출력 예 설명

입출력 예 #1

• 다음 그림은 주어진 입력을 해결하는 방법 중 하나를 나타낸 것입니다.

• 4번과 7번을 연결하는 전선을 끊으면 두 전력망은 각 6개와 3개의 송전탑을 가지며, 이보다 더 비슷한 개수로 전력망을 나눌 수 없습니다.
• 또 다른 방법으로는 3번과 4번을 연결하는 전선을 끊어도 최선의 정답을 도출할 수 있습니다.

입출력 예 #2

• 다음 그림은 주어진 입력을 해결하는 방법을 나타낸 것입니다.

• 2번과 3번을 연결하는 전선을 끊으면 두 전력망이 모두 2개의 송전탑을 가지게 되며, 이 방법이 최선입니다.

입출력 예 #3

• 다음 그림은 주어진 입력을 해결하는 방법을 나타낸 것입니다. 

• 3번과 7번을 연결하는 전선을 끊으면 두 전력망이 각각 4개와 3개의 송전탑을 가지게 되며, 이 방법이 최선입니다.

 

📝 문제 해결

인접 행렬 이용해 그래프를 표현해주고

1) 전선을 하나씩 끊어 전력망을 두개로 분리시켜

2) 두 전력망의 송전탑 개수의 차이를 구하고

(➡️ BFS를 사용해 끊어진 전력망 중 하나를 선택하여 연결된 노드의 수를 구해준다.)

3) 최솟값을 갱신해주면 된다.

💻 코드

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    static int[][] graph;
    
    public int solution(int n, int[][] wires) {
        int answer = n;
        graph = new int[n+1][n+1];
        
        for(int i=0; i<wires.length; i++){
            int from = wires[i][0], to = wires[i][1];
            graph[from][to] = 1;
            graph[to][from] = 1;
        }
        
        for(int i=0; i<wires.length; i++){
            int from = wires[i][0], to = wires[i][1];
            graph[from][to] = 0;
            graph[to][from] = 0;
            
            answer = Math.min(answer, bfs(n, from));
            graph[from][to] = 1;
            graph[to][from] = 1;
            
        }
        return answer;
    }
    
    public static int bfs(int n, int x){
        boolean[] visited = new boolean[n+1];
        int count = 1;
        
        Queue<Integer> que = new LinkedList<Integer>();
        visited[x] = true;
        que.offer(x);
        
        while(!que.isEmpty()){
            int temp = que.poll();
            
            for(int i=1; i<=n; i++){
                if(graph[temp][i] == 1 && !visited[i]){
                    visited[i] = true;
                    que.offer(i);
                    count ++;
                }
            }
        }
        
        return (int)Math.abs(count-(n-count));
    }
}