hansjour 개발일지

https://www.acmicpc.net/problem/2667  문제 파악-네트워크 문제와 비슷하게, 연결 된 집을 갯수를 모두 카운트하고-한 단지가 끝나면 다른 단지도 순회한다.-N X N 크기 접근 방법-DFS로 탐색(재귀 탐색)-탐색 후 visited 체크(혹은 0으로 변경?)-재귀 호출 일어날 때마다 cnt증가, 종료될 때마다 cnt합산-다른 집 옮겨갈 때 dfs 사용한다. (dfs 한번 당 1)-결과값은 재귀호출 내에서 관리하는 것이 아니라매 dfs마다 새로운 변수를 만들어 타고타고 누적하며 그 값을 리턴하면 1씩 누적되는 형태(모아서 바치는 형태로 생각하자.)-DFS함수는 int형태를 리턴하고, 한 단지의 순회가 끝나면 모아모아 받은 결과값을 메인함수에서 저장 코드 구현import java..

https://www.acmicpc.net/problem/2644   문제 파악-총 노드 갯수 n-특정 노드 a,b (a: start, b: target)-간선 m-~연결관계~ : 단방향(부모-자식 관계 명확)*StringTokenizer는 문자열 한 줄에서만 유효, 여러 줄일 시 새로운 st 선언해줘야 한다. *또한 띄어쓰기가 있는 문자열 쪼개는 데 쓴다.*br.readLine으로 받아서 해당 String.charAt()으로 받는 건 띄어쓰기가 없을 경우에 사용! 접근 방법-BFS함수 별도 작성-시작점a로부터 도착노드b까지 top-bottom이 명확한 그래프이지만, 위로 거슬러 올라가는 로직을 별도로 추가하여4방향 탐색하듯이 (경우 따져보고 전진), 가능하면 전진하여 카운트하고 아니면 그 다음 경우로 ..

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번부터 시작, ..