hansjour 개발일지

문제 파악-시작점(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..

N-Queen  코드 구현import java.util.*;class Solution { int cnt=0; public int solution(int n) { //가로 세로 같은 줄에 있음 안되고, //대각선에 겹침 안됨.. //퀸 놓을 때마다 카운트, 말==n이면 카운트 //조건 뚫고 n개 다 놓을 수 있는 경우의 수를 구하기 //부모row != 자식row //부모col != 자식col //[row+1][col-1] || [row+1][col+1] => 대각선 //혹은 Math.abs(line[i]-col)==Math.abs(i-row) 여기서 i는 변하는 row값 int[] l..

https://leetcode.com/problems/word-search/  >접근 방법-dfs(backtrack)을 이용한 풀이dfs함수의 리턴값을 boolean으로 주어 방향마다 전진 가능한지 여부 체크-해당 노드가 유효하려면, 전진이 가능한지 여부도 체크해야함.-isValid() 조건 1) 범위 벗어나면X 2) 방문했으면X 3) charAt(idx)와 같아야함-재귀적으로 dfs 메서드 호출하고 하나라도 true를 반환하면 전체 탐색을 멈추고 true를 반환한다. 리턴되지 못하고 빠져나오면 false라는 의미이므로 방문 취소하고 다른 경우의 수 탐색-최종 리턴값이 boolean타입이기 때문에 dfs도 boolean타입인 게 헷갈리지 않음코드 구현class Solution { public boo..