매일 조금씩

BFS의 대표적인 유형중 하나인, 빠른 탈출 문제이다.메모리 효율을 위해 visited 객체를 따로 생성해서 쓰지않고 방문한 곳은 주어진 그래프에서 값을 업데이트 하는 방식으로 했다. class Solution { public int nearestExit(char[][] maze, int[] entrance) { int rows = maze.length; int cols = maze[0].length; Queue queue = new LinkedList(); queue.offer(entrance); // 이렇게 지나온 곳을 장애물로 표시하고 지나가면 // visited 관련 객체를 따로 관리 하지 않아도돼서 메모리를 아낄수..

이 문제도 방향성이 있는 그래프 문제와 다름이 없다. 노드간 방향성이 있는 그래프로 그려보면..각 간선을 연결하면 곱이라는 연산으로 정의 내려질수 있고,기존 방향과 반대 방향의 가중치는 진입 차수 배열에 1/(가중치)로 저장되면 된다.a/b = 2 이고, b/c = 2일때, a/c == (a/b) * (b/c) 이기 때문..  class Solution { public double[] calcEquation(List> equations, double[] values, List> queries) { double[] finalAns = new double[queries.size()]; // 노드와 그에 연결된 간선들을 저장 HashMap> map = new Hash..

방향성이 있는 그래프에서 진입차수 배열에 주어진 방향의 반대방향도 넣어두는 것이 포인트이다.다만 이 반대방향이 주어진 방향을 뒤집은 방향이라는 것을 알게 하기 위해 음수로 저장했다. class Solution { public int minReorder(int n, int[][] connections) { List> al = new ArrayList(); boolean[] visited = new boolean[n]; for(int i = 0; i ()); } // 한 방향에 대해서 양방향으로 저장함. // 이때, 시작점에서 나가는건 양수, 반대는 음수로 저장. // => 여기선 시작점인 0 부터 차차 탐색하기 때..

이문제는 dfs, bfs 로 풀수도 있지만 HashSet 객체를 활용해서 문제를 해결했다.  class Solution { public int longestConsecutive(int[] nums) { Set numSet = new HashSet(); for (int num : nums) { numSet.add(num); } int longest = 0; for (int num : nums) { if (!numSet.contains(num - 1)) { int length = 1; // num이 연속된 수의 시작일 떄 ..

특정과목을 수강하려면 선행과목을 수강해야 할수있는데. 주어진 모든 과목을 수강할 수 있는지 확인하는 문제다.이문제는 dfs, bfs 둘 다 풀수 있으나, bfs가 좀 더 효율적이고 직관적이다. 맨처음 문제를 보았을 땐 dfs 로 풀어야겠다는 생각을 했지만.. bfs가 더났다. 먼저, 이문제의목표는 .. 주어진 n개의 과목을 모두 수강할 수 있는지, 즉 사이클 없이 모든 과목을 완료할 수 있는지를 확인하는 것이다.이를 위해 prerequisites라는 선행 과목의 제약 조건이 주어지며, 이 조건을 만족할 수 있는 순서대로 모든 과목을 수강할 수 있는지를 판단해야한다. bfs가 더 적합한 이유는 위상 정렬과 사이클 검출이 자연스럽기 때문이다.이 문제는 방향 그래프에서 사이클이 있는지 확인하는 문제로 볼 수 ..

class Solution { public boolean canJump(int[] nums) { int goal = nums.length - 1; // dp는 무조건 배열의 앞에서부터 찾아나간다고 생각했는데 // 여기선 최대 점프수가 주어지니까 골 지점 바로 앞에서시작해서 --하며 시작점까지 도달가능한지 역추적한다.. // goal에 도달가능한 지점이면 goal해당 지점으로 업데이트한다. // 업데이트 되는 goal에 계속 도달가능해서 goal이 계속 앞으로 이동하면. // 거쳐온 모든 뒤의 인덱스들을 통해 무조건 마지막 지점에 도착할수 있으므로 젤 앞의(현재의) goal만 봐도 무방함. for(int i = ..