[056] 알고리즘: 암시적 그래프

 
2024.07.26(금)
 
알고리즘 5일차

특강이기에
세부 내용은 노션에 기록
티스토리에는 출퇴근 복습용 코드만 기록
 

---

Graph
: 접점과 연결관계만 있으면 그래프 표현 가능
 
1) 인접 행렬 : 연결된 노드를 0, 1로 표현 ex) 1: [0,0,1,1,0]
2) 인접 리스트: 연결된 노드들의 목록 ex) 1:  [3, 4]

3) 암시적 그래프: 노드와 간선이 명시 X, 필요에 따라 동적으로 생성되는 그래프  
    ㄴ 그리드를 그래프적으로 해석 / 모든 그리드가 그래프인 것은 아님
 
- 그래프 순회(Traversal): 모든 노드를 방문 #일촌
- 그래프 탐색(Search): 특정 조건을 만족하는 노드 찾기

암시적 그래프
: 시작점에 연결된 모든 정점 탐색
 
방향 선택
- BFS와 그리드 비교
그리드는 방향이 없기 때문에 아래와 같이 하나하나 들어가야함

for(int i = 0; i < 8; i ++){
   int nextRow = curRow = dr[i];
   int nextCol = curCol + dc[i];
    if(isValid(nextRow, nextCol)){
      if(!visited[nextRow] [nextCol]){
         queue.offer(nex int[]{nextRow, nextCol});
         visited[nextRow] [nextCol] = true;

 
- DFS와 그리드 비교
: 재귀를 이용해서 자신의 역할을 다음으로 미룸
 
▼ DFS 예시

static Map<Integet, List<Integer>> graph = new HashMap<>();
static Map<Integer, Boolean> visited = new HashMap<>();

public static void dfs(int curVertex){
   visited.put(curVertex, true);
   for(int nextVertex: graph.get(curVertex)){
      if(!visited.containsKey(nextVertex){
         dfs(nextVertex);
         }
      }
   }
   
   public static void main(String[] agrs){
      makeGraph();
      dfs(0);
      }

 

오늘 이건 외우자!

 
▼ Number of islands

class Solution {
    int[] dr = {1, -1, 0, 0};
    int[] dc = {0, 0, 1, -1};
    int rowLength;
    int colLength;
    public int numIslands(char[][] grid) {
        rowLength = grid.length;
        colLength = grid[0].length;
        int count = 0;
        boolean[][] visited = new boolean[rowLength][colLength];

        for (int r = 0; r < rowLength; r++){
            for (int c = 0; c < colLength; c++){
                if (grid[r][c] == '1' && !visited[r][c]){
                    dfs(r,c, grid, visited);
                    count += 1;
                }
            }
        }
        return count;
    }
    void bfs(int r,int c){

    }
    void dfs(int r,int c, char[][] grid, boolean[][] visited){
        visited[r][c] = true;

        for (int i = 0 ; i < 4; i++){
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (0 <= nr && nr < rowLength && 0 <= nc && nc < colLength && grid[nr][nc] == '1'){
                if (!visited[nr][nc]){
                    dfs(nr,nc, grid, visited);
                }    
            }
        }
    }
}

 
▼ 거리두기 확인하기

import java.util.*;

class Solution {
    private static final int[] dr = {1, -1, 0, 0};
    private static final int[] dc = {0, 0, 1, -1};
    
    public int[] solution(String[][] places) {
        int n = places.length;
        int[] answer = new int[n];
        
        for (int i = 0; i < n; i++) {
            if (check(places[i])) {
                answer[i] = 1;
            } else {
                answer[i] = 0;
            }
        }
        
        return answer;
    }

    // 모든 사람이 거리두기를 잘 하고 있는지 체크하는 함수
    boolean check(String[] place) {
        for (int r = 0; r < 5; r++) {
            for (int c = 0; c < 5; c++) {
                if (place[r].charAt(c) == 'P') {
                    if (!bfs(r, c, place)) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    // 거리 2 이하에 사람이 있는지 확인하는 BFS 함수
    boolean bfs(int r, int c, String[] place) {
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{r, c, 0}); // 시작점과 거리 0
        boolean[][] visited = new boolean[5][5];
        visited[r][c] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int cr = cur[0];
            int cc = cur[1];
            int dist = cur[2];

            // 거리 2 이상이면 더 이상 탐색하지 않음
            if (dist > 2) continue;

            // 거리 2 이하의 위치에서 사람 발견 시 거짓 반환
            if (dist != 0 && place[cr].charAt(cc) == 'P') {
                return false;
            }

            for (int i = 0; i < 4; i++) {
                int nr = cr + dr[i];
                int nc = cc + dc[i];

                // 유효한 위치인지 확인하고, 방문하지 않았으며, 벽이 아닌 경우
                if (nr >= 0 && nr < 5 && nc >= 0 && nc < 5 && place[nr].charAt(nc) != 'X' && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    queue.offer(new int[]{nr, nc, dist + 1});
                }
            }
        }
        
        return true;
    }
}