<JAVA TIL20> 코트타카 모음집 | dfs 문제 3개

📌 내일배움캠프 4/8 TIL

<JAVA TIL20> 코트타카 모음집 ❘ dfs 문제 3개

 

---

코드타카

어쩌다 보니 밀린 코트타카 문제들을 모아서 올리게 되었다

주말 복습 아자아자

 

[행렬 테두리 회전하기]

• DFS 

import java.util.*;

class Solution {
    int[][] map;
    ArrayList<Integer> list = new ArrayList<>();
    
    public int[] solution(int rows, int columns, int[][] queries) {
        map = new int[rows][columns];
        int index = 1;
        for(int i=0; i<rows; i++) {
            for(int j=0; j<columns; j++) {
                map[i][j] = index++;
            }
        }
        
        for(int i=0; i<queries.length; i++) {
            int sx = queries[i][0]-1;
            int ex = queries[i][2]-1;
            
            int sy = queries[i][1]-1;
            int ey = queries[i][3]-1;
            
            dfs(sx, ex, sy, ey);
        }
        
        int[] answer = new int[list.size()];
        for(int i=0; i<list.size(); i++) {
            answer[i] = list.get(i);
        }

        return answer;
    }
    
    private void dfs(int sx, int ex, int sy, int ey) {
        int cur = map[sx][sy];
        int min = cur;
        
        for(int i=sx; i<ex; i++) {
            map[i][sy] = map[i+1][sy];
            min = Math.min(min, map[i][sy]);
        }
        
        for(int i=sy; i<ey; i++) {
            map[ex][i] = map[ex][i+1];
            min = Math.min(min, map[ex][i]);
        }
        
        for(int i=ex; i>sx; i--) {
            map[i][ey] = map[i-1][ey];
            min = Math.min(min, map[i][ey]);
        }
        
        for(int i=ey; i>sy; i--) {
            map[sx][i] = map[sx][i-1];
            min = Math.min(min, map[sx][i]);
        }
        
        map[sx][sy+1] = cur;
        list.add(min);
    }
}

 

프로그래머스

 

 

[전력망을 둘로 나누기]

• 완전 탐색

1. 좌표를 나눠서 끊어주는 방법

for(int[] w : wires) {
    int a = w[0];
    int b = w[1];

    list[a].remove(Integer.valueOf(b)); //좌표를 삭제하되, 인덱스를 지우지 않도록 형태 변환
    list[b].remove(Integer.valueOf(a));

    visited = new boolean[n+1]; //visited 배열 초기화
    int size1 = count(a); //덩어리 하나의 크기를 확인
    int size2 = n-size1;
    answer = Math.min(answer, Math.abs(size1-size2)); //작은 값이면서, 절대값

    list[a].add(b); //원상복귀
    list[b].add(a);
}

 

2. 크기 확인 방법

private int count(int a) { //리턴은 숫자로
    visited[a] = true; //방문 처리
    int c = 1; //하나의 dfs당 1씩 리턴

    for(int i : list[a]) {
        if(!visited[i]) {
            c += count(i); //값들을 누적해줌
        }
    }

    return c;
}

 

프로그래머스

 

 

[배달]

• Graph + BFS
  • Arrays.fill을 사용해서 visited배열에 최대값을 넣어준다
  • BFS를 돌면서, Math.min()을 사용해서 최소값이 들어가도록 해준다

import java.util.*;

class Solution {
    ArrayList<int[]>[] graph;
    int[] visited;
    
    public int solution(int N, int[][] road, int K) {
        graph = new ArrayList[N+1];
        visited = new int[N+1];
        int answer = 0;
        Arrays.fill(visited, Integer.MAX_VALUE);
        
        for(int i=1; i<=N; i++) {
            graph[i] = new ArrayList<>();
        }
        
        for(int i=0; i<road.length; i++) {
            int a = road[i][0];
            int b = road[i][1];
            int c = road[i][2];
            
            graph[a].add(new int[]{b, c});
            graph[b].add(new int[]{a, c});
        }
        
        visited[1] = 0;
        Queue<Integer> q = new LinkedList<>();
        for(int[] g : graph[1]) {
            int a = g[0];
            int b = g[1];
            visited[a] = Math.min(visited[a], b);
            q.add(a);
        }
        
        while(!q.isEmpty()) {
            int cur = q.poll();
            for(int[] c : graph[cur]) {
                int a = c[0];
                int b = c[1];
                
                if(visited[a] > visited[cur]+b) {
                    visited[a] = visited[cur]+b;
                    q.add(a);
                }
            }
        }
        
        for(int i=0; i<visited.length; i++) {
            if(visited[i] <= K) {
                answer++;
            }
        }
        
        return answer;
    }
}

 

 

프로그래머스