hansjour 개발일지

https://leetcode.com/problems/number-of-islands/ 문제 파악-2차원 배열이 주어지고, 1이 상하좌우로 있는지 체크하여 섬이 총 몇 개 있는지 센다. (분기체크)m == grid.lengthn == grid[i].length1 grid[i][j] is '0' or '1'.접근 방법-0은 물, 1은 섬. 물 만나거나 범위 벗어나지 않는 이상, 섬 한 덩어리로 본다.-1이면 계속 순회하며 visit 체크(무한 루프 방지)-처음 기준 노드는 ‘1’ 나오면 시작. 타고 가서 상하좌우 dfs 체크⇒ 막히면 return되고, 다른 방향으로 탐색 시작-If 0이거나, 벽이면 순회 끝(base case)코드 구현import java.util.*;class Solution { p..

https://leetcode.com/problems/shortest-path-in-binary-matrix/description/문제 파악-방향을 탐색하는 문제-최소 거리를 구하는 BFS문제n == grid.lengthn == grid[i].length1 grid[i][j] is 0 or 1 접근 방법💡 -좌표 (x,y) -큐에서 poll()하여 방향에 따라 더하거나 뺀다.-8방향은 0,0 기준점을 기준으로 둘러싼 방향-8방향을 2차원 배열로 미리 선언해두어 for문으로 조회하고 현재 값에 더한다.1)시작점 혹은 끝점이 0이 아니거나,2) 끝점까지 가는 명확한 길이 없다면 즉, 큐 순회가 끝날 때까지 끝점에 도달하지 못하고 가는 길이 끊긴다면⇒ -1 리턴 코드 구현class Solution { ..

문제 파악-시작점(1,1)에서 도착점(n,m)까지 최단 거리를 구하기maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.접근 방법💡 -배열은 (0,0)부터인데 지문은 (1,1)이기 때문에 일관성있게 0based index유지해야함-(첫트) DFS : Integer.MAX_VALUE로 최대한 큰 값 넣어..

문제 파악-시작점에서 도착지점까지 한 칸씩 이동하며 카운트하기-레버 만나야 도착지점으로 갈 수 있음5 ≤ maps의 길이 ≤ 1005 ≤ maps[i]의 길이 ≤ 100maps[i]는 다음 5개의 문자들로만 이루어져 있습니다.S : 시작 지점E : 출구L : 레버O : 통로X : 벽시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.  접근 방법-시작점 S가 어디에 있는지 먼저 찾아서 거기서부터 각 방향으로 갈 수 있는지 유효성 검사(isValid)-갈 수 있는 방향 따라 가면서 큐에 가능한 경로 좌표 담기-bfs를 활용해 도착지점까지 최소거리 구하기(큐에 담을 때는 x..

https://leetcode.com/problems/keys-and-rooms/description/ 문제 파악-0번 room부터 순회하며 key를 획득하고, 얻은 키를 가지고 방을 순회. 순회하지 못한 방이 하나라도 있다면 return false.n == rooms.length2 0 1 0 All the values of rooms[i] are unique. 접근 방법(첫번째 시도)💡 -방 하나 당 우선 key를 획득하고, 그 다음 차례대로 방을 넘어가므로 bfs를 이용해 풀이-주어진 리스트를 해시맵 형태로 변환하고 bfs 함수를 만들어 순회한다.-0은 시작할 때 방문을 열어주는 것과 같으므로, 조건문을 통해 visited에 기본적으로 집어넣는다. 접근 방법(개선 사항)💡 -방 하나 당 우선 ke..

https://leetcode.com/problems/is-graph-bipartite/  문제 파악-0~n까지의 노드가 주어지고 각 노드의 간선 status가 주어짐-이분 그래프 true or false 찾아라graph.length == n1 0 0 graph[u] does not contain u.All the values of graph[u] are unique.If graph[u] contains v, then graph[v] contains u.접근 방법-이분 그래프 :두 개의 독립된 집합으로 정점을 나눌 수 있다.모든 간선이 한 집합의 정점과 다른 집합의 정점을 연결해야 한다.-"독립적"이라는 말은 같은 그룹의 정점들끼리는 직접 연결된 간선이 없다는 뜻⇒ 그래프를 돌며 노드 하나씩 순회 → 순..

https://leetcode.com/problems/coin-change/description/ 문제 파악-트리를 타고 내려가며 주어진 amount값을 최소한의 갯수로 채우기-dfs를 활용한 그리디 알고리즘으로 해석1 1 0 접근 방법-(최적) 그리디 알고리즘-(차선) 일단, 동전 금액이 큰 것부터 적용시켜야 유리하므로 정수 배열 내림차 순 정렬하기-dfs함수 구현(total은 0에서 시작, 경우의 수에 따라 누적해가기 and backtrack())-금액이 들어가면 리스트에 누적해가다가 total이 amount와 동일해지면 return,그렇지 않으면 recursive 또 돌면서 total 누적해가기코드 구현(그리디)import java.util.*;class Solution { public int..

문제 파악-n개의 노드가 주어지고, n개의 노드와 연결 된 노드의 인덱스에 연결이 유효하면 1, 유효하지 않으면 0을 표시한다.컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.각 컴퓨터는 0부터 n-1인 정수로 표현합니다.i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.computer[i][i]는 항상 1입니다.접근 방법💡-DFS 통해 인접한 노드 순회하고, 인접 없으면 네트워크 끝.그런 네트워크가 몇개인지 총 카운트 (DFS를 네트워크만큼 수행)-2차원 배열의 형태로 주어지는 연결 값을 보고, 각 노드가 어디와 연결되었는지 먼저 파악한다. -코드 작성의 원활함을 위해 셋 그래프를 인접 리스트 형태로 변환, O(n^2)-start노드는 1번부터 시작, ..

코드 구현import java.util.*;class Solution { public int solution(String begin, String target, String[] words) { Queue queue = new ArrayDeque(); boolean[] visited = new boolean[words.length]; queue.offer(new WordState(begin,0)); //방문 체크는 안해도 됨 while (!queue.isEmpty()){ //방문 (가까운 곳부터) WordState curr = queue.poll(); //방문한 곳이 내가 찾던 t..

문제 파악-주어진 배열을 끝까지 돌며 +,- 두 가지를 모두 구해 target값에 다다르는 경우의 수를 카운트주어지는 숫자의 개수는 2개 이상 20개 이하입니다.각 숫자는 1 이상 50 이하인 자연수입니다.타겟 넘버는 1 이상 1000 이하인 자연수입니다.접근 방법-완전 탐색이라서 dfs도 가능하지만, 큐가 조금 더 익숙해 큐로 풀이했다.-기준 뽑아 연결 된 노드(경우의 수)를 모두 큐에 넣고 같은 조건에서 값을 누적해나갔을 때 결과값을 비교-결과값이 맞기만 하면 카운트하면 되므로, 그냥 카운트한다.코드 구현import java.util.*;class Solution { public int solution(int[] numbers, int target) { Queue que=new Ar..