231115 - DFS/BFS : 백트래킹, 연결된 노드 확인, matrix 칸값 누적, 도형 테두리, 재귀문 문자 리턴 받는 팁

[robert-min]

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

타겟 넘버

• 풀이 1.depth가numbers 길이가 될때까지 탐색

class Solution {    
    static int answer, n;

    // 1
    public void dfs(int[] numbers, int target, int depth, int S) {
        if (depth == n) {
            if (S == target) {
                answer++;
            }
            return;
        } else {
            dfs(numbers, target, depth+1, S + numbers[depth]);
            dfs(numbers, target, depth+1, S - numbers[depth]);
        }

        return;    
    }

    public int solution(int[] numbers, int target) {
        answer = 0;
        n = numbers.length;
        dfs(numbers, target, 0, 0);

        return answer;
    }
}

[robert-min]

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

네트워크 (연결된 노드 확인)

• 풀이
  1. graph에 연결된 간선 입력
  2. 아직 방문되지 않는 노드는 이전에 연결되지 않은 노드 이기 때문에 탐색이 필요.
  3. DFS로 연결된 노드 탐색
  4. 새로 탐색할 때마다 answer++

import java.util.*;

class Solution {

    static List<ArrayList<Integer>> graph;
    static boolean[] visited;

    // 3
    static void dfs(int start) {
        if (!visited[start]) {
            visited[start] = true;
            for (int nx : graph.get(start)) {
                dfs(nx);
            }
        }
    }

    public int solution(int n, int[][] computers) {
        int answer = 0;

        // 1
        graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;

                if (computers[i][j] == 1) {
                    graph.get(i).add(j);
                }
            }
        }
        // System.out.println(graph);

        // 2
        visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i);
                // 4
                answer++;
            }
        }

        return answer;
    }
}

[robert-min]

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

게임 맵 최단거리(matrix 칸값 누적)

• 주의 : nn 이아닌 nm임을 확인
• 풀이
  1. BFS로 0,0 부터 전체 탐색 탐색하면서 이전 값에 +1해주면서 칸 개수 계산
  2. 찾으려는 칸이 0이면 -1, 아니면 해당 값 리턴

import java.util.*;

class Solution {
    static int n, m;
    static int[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static void bfs(int x, int y, int[][] maps) {
        Queue<int[]> Q = new LinkedList<>();
        Q.add(new int[]{x, y});
        visited[x][y] = 1;

        while (!Q.isEmpty()) {
            int[] now = Q.poll();
            for (int k = 0; k < 4; k++) {
                int nx = now[0] + dx[k];
                int ny = now[1] + dy[k];

                if (nx < 0 || ny < 0|| nx >= n || ny >= m || maps[nx][ny] == 0) continue;

                if (visited[nx][ny] == 0) {
                    Q.add(new int[]{nx, ny});
                    visited[nx][ny] += visited[now[0]][now[1]] + 1;
                }
            }
        }

    }

    public int solution(int[][] maps) {
        int answer = 0;

        // 1
        n = maps.length;
        m = maps[0].length;
        visited = new int[n][m];
        bfs(0, 0, maps);
        // System.out.println(Arrays.toString(visited[n-1]));

        // 2
        if (visited[n-1][m-1] == 0) {
            return -1;
        }

        return visited[n-1][m-1];
    }
}

[robert-min]

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

단어 변환

• 풀이
  1. begin 부터 탐색. 하나의 단어만 다른지 확인 후 다를 경우 변경
     • 중복 탐색을 막기위해 이미 탐색한 단어는 다시 탐색하지 않도록 visited에 기록 저장
  2. 정답 리턴

import java.util.*;

class Solution {
    static int min, n;
    static boolean[] visited;

    static boolean check(String word1, String word2) {
        int idx = 0;
        for (int j = 0; j < word1.length(); j++) {
            if (word1.charAt(j) != word2.charAt(j)) idx++;
            if (idx >= 2) return false;
        }
        if (idx == 1) return true;
        return false;
    }

    static void dfs(String now, String target, String[] words, int cnt) {
        // String 비교는 equals
        if (now.equals(target)) {
            min = Math.min(min, cnt);
        } else {
            for (int i = 0; i < n; i++) {
                if (!visited[i]) {
                    String word = words[i];   
                    if (check(now, word)) {
                        visited[i] = true;
                        dfs(word, target, words, cnt + 1);
                        visited[i] = false;
                    }
                }
            }
        }

    }

    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        n = words.length;
        min = n;
        visited = new boolean[n];
        // 1
        dfs(begin, target, words, 0);

        // 2
        if (min == n) {
            return 0;
        }
        return min;
    }
}

[robert-min]

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

아이템줍기(도형 테두리)

• 풀이
  1. 직사각형 둘레에만 입력
  2. BFS로 탐색

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

class Solution { static int[][] map; static int answer; //character->item(목표 포인트) public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) { answer=0;

    //1) map을 만든다.
    map= new int[101][101];

    //2) 좌표에 따라 map에 값을 넣을건데, 테두리에만 1을 넣을것이다.(*좌표는 두배로)
    for(int i=0; i<rectangle.length; i++){
        fill(2*rectangle[i][0], 2*rectangle[i][1], 2*rectangle[i][2], 2*rectangle[i][3]);
    }

    //3) bfs로 테두리 따라 양쪽으로 가보고 min값 채택
    bfs(2*characterX, 2*characterY, 2*itemX, 2*itemY);

    return answer/2;
}

//x1,y1,x2,y2 => (x1,y1)~(x2,y1), (x1,y2)~(x2,y2), (x1,y1)~(x1,y2), (x2,y1)~(x2,y2)
//편하게 x2 해준 좌표를 받는다.
public void fill(int x1, int y1, int x2, int y2){
    for(int i=x1; i<=x2; i++){
        for(int j=y1; j<=y2; j++){
            if(map[i][j]==2) continue;
            map[i][j]=2;
            if(i==x1||i==x2||j==y1||j==y2){
                map[i][j]=1;
            }
        }
    }
}//fill

static int[] dx= {-1, 0, 0, 1};
static int[] dy= {0, -1, 1, 0};
public void bfs(int startx, int starty, int itemx, int itemy){
    boolean[][] visited= new boolean[101][101];
    Queue<Integer> queue= new LinkedList<>();
    queue.add(startx);
    queue.add(starty);

    while(!queue.isEmpty()){
        int x= queue.poll();
        int y= queue.poll();

        for(int i=0; i<4; i++){
            int nx= x+dx[i];
            int ny= y+dy[i];
            if(!check(nx, ny)) continue; //범위 아웃
            if(map[nx][ny]!=1||visited[nx][ny]) continue;

            //map[nx][ny]==2이고 방문한적없음
            map[nx][ny]=map[x][y]+1;
            if(nx==itemx&&ny==itemy){ //목표점 도달
                answer= (answer==0)? map[nx][ny]:Math.min(answer,map[nx][ny]);
                continue;
            }
            visited[nx][ny]= true;
            queue.add(nx);
            queue.add(ny);
        }
    }
}//bfs

public boolean check(int x, int y){
    if(x<0||y<0||x>100||y>100) return false;
    return true;
}

}

[robert-min]

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

여행경로 (재귀문 문자 리턴 받는 팁)

• 풀이 : 주석 참조

  import java.util.*;
  class Solution {
  static boolean[] visited;
  static Queue<String> Q = new PriorityQueue<>();
  
  static void dfs(String[][] tickets, String now, int cnt, String path) {
      // 2. 경로만 나와 있기 때문에 now를 기준으로 탐색하고 모든 tickets를 탐색하면 종료
      if (cnt == tickets.length) {
          Q.add(path);
          return;
      } 
      for (int i = 0; i < tickets.length; i++) {
          if (!visited[i] && now.equals(tickets[i][0])) {
              visited[i] = true;
              dfs(tickets, tickets[i][1], cnt + 1, path + "," + tickets[i][1]);
              visited[i] = false;
          }
      }
  }
  
  public String[] solution(String[][] tickets) {
      String[] answer;
  
      visited = new boolean[tickets.length];
  
      //1 : 시작점 ICN 부터 탐색
      dfs(tickets, "ICN", 0, "ICN");
      //3 : 재귀문에서 String을 빼기에 어려움이 있으니 해당 값을 큐에 넣고 나중에 빼는 방법 사용;
      answer = Q.peek().split(",");
  
      return answer;
  }
  }