hansjour 개발일지

문제 파악-시작점에서 도착지점까지 한 칸씩 이동하며 카운트하기-레버 만나야 도착지점으로 갈 수 있음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..

https://leetcode.com/problems/permutation-sequence/  문제 파악1~n 까지의 수의 순열을 구하고, 그 중 k번째 순열을 문자열 형태로 리턴1 1 접근 방법-순열 문제코드 구현import java.util.*;class Solution { public String getPermutation(int n, int k) { String answer=""; List> permutations = new ArrayList(); boolean[] visited = new boolean[n]; String[] arr = new String[n]; for(int i=1;i(),visited,n,arr); ..