지니로그

오늘의 학습 키워드

그래프, BFS

알고리즘 문제

• 프로그래머스 Level 3. 가장 먼 노드
• https://school.programmers.co.kr/learn/courses/30/lessons/49189 

공부한 내용

Tree 자료 구조

• Parent - Child 관계를 나타낼 수 있는 자료구조
• 노드 한 개에 1개의 Parent 노드가 있을 수 있다.
• 노드 한 개에 N개의 Child 노드가 있을 수 있다. 
• e.g.) 폴더, 조직도, 가족 관계도
• Binary Tree: 노드 한 개에 최대 2개의 Child 노드를 가질 수 있는 자료구조. => 왼쪽 Child 노드, 오른쪽 Child 노드.

class Node {
    int value;
    Node next;
    
    Node(int val) {
        this.value = val;
        this.next = null;
    }
}

class BinaryNode {
    int value;
    BinaryNode leftChild;
    BinaryNode rightChild;
    
    BinaryNode(int val) {
    	this.value = val;
        this.leftChild = null;
        this.rightChilde = null;
    }
}

DFS

• 한 방향을 먼저 쭉 탐색하고, 그 후에 다음 노드로 올라와서 쭉 탐색한다.
• 재귀 (Reculsive)로 간단하게 구현 가능.

BFS

• Level 별로 탐색한다. 루트노드로부터 1칸 떨어진 노드들 탐색 -> 2칸 떨어진 노드들 탐색 -> ... 
• Queue 자료구조로 구현 가능.
  • 처음에 시작할 루트노드를 queue에 먼저 넣는다.
  • 이후에 큐가 비어있지 않으면 계속 반복하면서 탐색한다.
  • 일반적으로 탐색 종료 조건은 큐의 사이즈가 0. 즉, 큐가 비어있으면 탐색 종료를 의미한다.

오늘의 회고

처음 시도

• 이전에 BFS, DFS 개념은 알고 있었지만 막상 알고리즘을 짜려고 보니 아직 개념이 부족하다고 느껴서 다시 Tree 자료구조에 대해 공부했다.
• BFS, DFS 개념을 다시 보니 이번 문제는 BFS로 풀면서 정해진 루트노드 1부터 시작해서 depth 별로 탐색하면서 depth마다 노드가 몇 개인지 카운트를 해야 한다고 생각했다.

해결

• BFS로 문제를 풀 때, 먼저 자료구조 Queue를 사용하면 depth 별로 queue에 담을 수 있어서 편리하다.
• BFS 문제 풀 때, 방문한 노드 체크 배열과 인접 행렬(노드 간 연결 관계 2차원 배열)을 만들어서 탐색 관리를 한다.
  • 인접 행렬 => 노드 A와 노드 B 사이에 간선 존재 여부를 시간복잡도 O(1)로 조회할 수 있다. (1이면 존재)
  • 방문 체크 배열 => 총 노드 개수 +1 사이즈로 1차원 배열을 만들어서 방문했다면 true로 알 수 있다.
• 일반적으로 BFS 문제는 queue가 빈 경우를 탐색 종료 조건(반복문 종료)으로 사용한다. 
  • 이번 문제에서는 존재하는 마지막 depth에 노드 개수를 알아야 하기 때문에, depth를 반복할 때마다 큐의 사이즈를 업데이트하도록 했다.
  • 그리고 큐가 비어있다면, depth(노드들)이 더이상 존재하지 않기 때문에 종료하고, 마지막에 업데이트된 큐 사이즈가 마지막 depth의 노드 개수를 의미하게 된다.

문제 풀이

import java.util.*;

class Solution {
    //return: 1번 노드와 가장 멀리 떨어진 노드는?
    boolean[] visit;		// 해당 노드(배열 인덱스)에 이미 방문했는지 여부
    boolean[][] relative;	// 인접 행렬 (그래프 관계)
    
    public int bfs(int[][] edge) {
        Queue<Integer> que = new LinkedList<>();
        que.offer(1);
        visit[1] = true;
        
        for (int i = 0; i < edge.length; i++) {
            int x = edge[i][0];
            int y = edge[i][1];
            
            relative[x][y] = true;
            relative[y][x] = true;
        }
		
        int size = 0;
        while (!que.isEmpty()) {
            size = que.size();
            
            for (int i = 0; i < size; i++) {
                int current = que.poll();
                
                for (int j = 1; j < visit.length; j++) {
                    if (!visit[j] && relative[current][j]) {
                        que.add(j);
                        visit[j] = true;
                    }
                }
            }
        }
        return size;
    }
    
    public int solution(int n, int[][] edge) {
        int answer = 0;
        
        this.visit = new boolean[n+1];
        this.relative = new boolean[n+1][n+1];
        
        answer = bfs(edge);
        
        return answer;
    }
}

오늘의 학습 키워드

BFS, 최단거리

알고리즘 문제

• 프로그래머스 Level 2. 게임 맵 최단거리
• https://school.programmers.co.kr/learn/courses/30/lessons/1844

공부한 내용

• BFS
• 최단 거리 알고리즘
• DFS vs BFS

오늘의 회고

처음 시도

•  경로 그려보면서 탐색 중단 케이스 확인해보기
  • 목표: (5,5)
    (1,1)->(1,2)=>벽(0)
    (1,1)->(2,1)->(2,2)=>벽(0)
    (1,1)->(2,1)->(3,1)->(3,2)=>벽(0)
    (1,1)->(2,1)->(3,1)->(4,1)->(4,2)->(4,3)->(4,4)=>벽(0)
    (1,1)->(2,1)->(3,1)->(4,1)->(4,2)->(4,3)->(5,3)=>벽(0)
    (1,1)->(2,1)->(3,1)->(4,1)->(4,2)->(4,3)->(3,3)->(3,4)->(3,5)->끝
    (1,1)->(2,1)->(3,1)->(4,1)->(4,2)->(4,3)->(3,3)->(3,4)->(3,5)->(4,5)->끝
    (1,1)->(2,1)->(3,1)->(4,1)->(4,2)->(4,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5) [골인] 
    (1,1)->(2,1)->(3,1)->(4,1)->(4,2)->(4,3)->(3,3)->(3,4)->(4,4)=>벽(0)
    (1,1)->(2,1)->(3,1)->(4,1)->(4,2)->(4,3)->(3,3)->(3,4)->(2,4)=>벽(0)
    (1,1)->(2,1)->(3,1)->(4,1)->(4,2)->(4,3)->(3,3)->(4,3)=> 왔던길
    (1,1)->(2,1)->(3,1)->(4,1)->(4,2)->(4,3)->(3,3)->(2,3)->(2,4)=>벽(0)
    (1,1)->(2,1)->(3,1)->(4,1)->(4,2)->(4,3)->(3,3)->(2,3)->(3,3)=>왔던길
    (1,1)->(2,1)->(3,1)->(4,1)->(4,2)->(4,3)->(3,3)->(2,3)->(1,3)->(1,4)->(1,5)=>끝
    (1,1)->(2,1)->(3,1)->(4,1)->(4,2)->(4,3)->(3,3)->(2,3)->(1,3)->(1,4)->(1,5)->(2,5)-> (3,5)->(4,5)->(5,5) [골인]
    (1,1)->(2,1)->(3,1)->(4,1)->(4,2)->(4,3)->(3,3)->(2,3)->(1,3)->(1,4)
    (1,1)->(2,1)->(3,1)->(4,1)->(4,2)->(4,3)->(3,3)->(2,3)->(1,3)->(2,3)=>왔던길
    (1,1)->(2,1)->(3,1)->(4,1)->(4,2)->(5,2)=>벽(0)
    (1,1)->(2,1)->(3,1)->(4,1)->(5,1)=>벽(0)
• 처음에 경로를 체크 해보면서, 경로 탐색 종료 조건인 경우를 확인해서 해봤던 탐색 방식인 DFS로 문제를 풀었다.
• 결과는 정확성 테스트는 통과, 효율성 테스트는 모두 실패했다.

class Solution {
	int[][] maps;
    int xMax;
    int yMax;
    int resultCount;
    
    // x,y 는 0,0부터 시작한다고 생각. 목표는 xMax, yMax
    public void dfs(int x, int y, int[][] visit, int count) {
    	// 동: x+1 / 서: x-1 / 남: y+1 / 북: y-1
        
        //종료 조건
        if (x > xMax || y > yMax || x < 0 || y < 0) return;	// 맵 벗어남
        if (visit[y][x] == 1) return;		// 왔던 길
        if (maps[y][x] == 0) return; 		// 벽
        if (x == xMax && y == yMax) {		// 목표 골인
            if (resultCount == -1 || count < resultCount) {	// 최단 거리 체크
                resultCount = count;
            }
            return;
        }
        
        count += 1;					//카운트
        visit[y][x] = 1;			//왔던길 체크
        
        dfs(x+1, y, visit, count);	//동쪽으로 이동
       	dfs(x, y+1, visit, count);	//남쪽으로 이동
        dfs(x-1, y, visit, count);	//서쪽으로 이동
        dfs(x, y-1, visit, count);	//북쪽으로 이동
        
        visit[y][x] = 0;			//백트래킹
    }
    
    public int solution(int[][] maps) {
        this.maps = maps;
   		this.xMax = maps[0].length-1;
   		this.yMax = maps.length-1;
		this.resultCount = -1;
        int[][] visit = new int[yMax+1][xMax+1];
        
        dfs(0, 0, visit, 1);
        
        return resultCount;
    }
}

해결

• 해결이 안되서 찾아보니 최단 거리 문제는 BFS가 더 효율성이 좋을 수 있다는 것을 알았다
• DFS의 경우 운이 좋으면 한 번에 경로를 찾을 수도 있지만, 운이 좋지 않는다면 효율성에서 최악의 시간복잡도가 나올 수 있기 때문

문제 풀이

• BFS
• DFS의 재귀 종료조건이 BFS에서 4방향 탐색에서 건너뛰는 조건으로 사용되었다.
• DFS와 최대 차이점: 한 길로 탐색 후 다른 길 탐색(DFS) vs 모든 방향 탐색 후 다시 모든 방향 탐색(BFS)
  • DFS는 재귀를 통해 한 방향으로 쭉 탐색하고 현재 경로가 유효하지 않거나 더 나은 경로를 찾기 위해 탐색을 종료하고 이전 상태로 돌아가야 하는 경우 백트래킹을 해줘야 한다. (깊이 우선)
  • BFS는 큐를 통해 모든 방향에 대한 좌표값을 큐에 담아서 백트래킹 필요없이 탐색 종료 조건에 걸리면 패스하고, 탐색할 수 있는 방향이면 방문 체크 & 큐에 담아서 탐색할 수 있도록 해준다. (너비 우선)

import java.util.*;

class Solution {
    public int solution(int[][] maps) {
        int[] dx = {1, -1, 0, 0};       // 동서남북 방향 벡터
        int[] dy = {0, 0, 1, -1};       // 동서남북 방향 벡터
        int xMax = maps[0].length - 1;  // x 좌표의 최대값
        int yMax = maps.length - 1;     // y 좌표의 최대값

        boolean[][] visit = new boolean[yMax + 1][xMax + 1]; // 방문 체크 배열
        Queue<int[]> queue = new LinkedList<>(); // BFS를 위한 큐
        queue.add(new int[] {0, 0, 1}); // 시작점 (0, 0)과 시작 거리 1을 큐에 추가
        visit[0][0] = true; // 시작점 방문 체크

        while (!queue.isEmpty()) {          // 큐가 비어있지 않으면 반복
            int[] current = queue.poll();   // 큐에서 현재 노드를 꺼냄
            int x = current[0];             // 현재 x 좌표
            int y = current[1];             // 현재 y 좌표
            int dist = current[2];          // 현재까지의 거리

            if (x == xMax && y == yMax) {   // 목표 지점에 도달하면
                return dist;                // 현재까지의 거리를 반환
            }

            for (int i = 0; i < 4; i++) {   // 동서남북 네 방향으로 탐색
                int nx = x + dx[i];         // 새로운 x 좌표
                int ny = y + dy[i];         // 새로운 y 좌표

                // 탐색 종료 조건(맵 벗어남, 벽, 재방문)
                if (nx < 0 || ny < 0 || nx > xMax || ny > yMax) continue;
                if (maps[ny][nx] == 0) continue;
                if (visit[ny][nx]) continue;

                visit[ny][nx] = true;                   // 방문 체크
                queue.add(new int[] {nx, ny, dist+1});  // 현재 좌표 큐에 추가
            }
        }

        return -1; // 큐를 다 돌고 목표 지점에 도달할 수 없는 경우
    }
}

Github