요깨비's LAB

노드 객체를 만들고 적절히 DFS 탐색하면서 부모노드를 갱신해주면 됩니다. 여기에서 이미 갱신된 부모노드는 갱신하지 않도록 예외를 걸어주었습니다. import java.util.ArrayList; import java.util.Iterator; import java.util.List; import java.util.Scanner; public class Main { static int N; static Element[] elements; static boolean[] visited; public static void main(String[] args) { Scanner scr = new Scanner(System.in); N = scr.nextInt(); elements = new Element[N + ..

처음 아이디어는 n을 이진수로 변환하여 저장하고 n+1의 값들을 이진수로 변환하여 이진수끼리 비교하여 1의 개수가 같은지를 비교하려했습니다. 하지만 이것은 값이 매우 커졌을때 매번 이진수 길이만큼 Brute-Force를 수행하기 때문에 시도하기 전에 답이 없겠다는 판단을 했습니다. 그래서 두번째 아이디어로 n의 값을 DFS연산을 하여 n%2, n/2를 이용하여 1인 경우만 체크하여 1의 개수를 count하여 저장. n의 값을 1씩 증가하여 똑같은 DFS연산을 수행한 count값이 n의 count값이 같은지를 비교하여 같으면 연산을 멈추고 답을 출력하는 방식으로 하였습니다. class Solution { public int solution(int n) { int answer = 0; int count = ..

방향그래프인 것을 생각하고, DFS를 이용하여 해결하였습니다. 로직은 아래와 같이 생각했습니다. 행렬에 값을 넣을때 1일 경우 해당 위치 값 x,y를 이용하여 Element객체를 만들어 Queue에 넣는다. Queue에서 Element를 하나 꺼낸다. 해당 위치를 Root로 두고 y는 현재 위치 x는 다음 위치로 DFS 연산을 진행한다. -> DFS 연산은 가리키는 곳이 값이 1이면서 방문하지 않은 곳이면 Root의 next 위치에서 다음 next 값들을 1로 바꿔준다.(이동 가능함을 체크한다는 의미) 그렇지 않으면 종료 -> 만약 Root값과 가리키는 값이 같으면 종료. 그려진 맵을 출력 아래에는 코드입니다. import java.util.LinkedList; import java.util.Queue;..

이번에도.. 오지게 오래 걸렸습니다... 순수 완벽하게 푼것이 아닌.. 백준 질문하기에서 반례들을 이용하면서 풀었구요.. 아직도 분기 처리 조건 생각하는거랑 로직을 제대로 생각 않하고 무작정 문제에 돌입하는 것... 참 안고쳐집니다. 좀만 풀이가 생각날 것 같으면 무조건 키보드에 손이 올라가는 이 흑우.. 처음 아이디어는 자료구조 Set 2개를 이용해서 DFS를 돌면서 각 방문 노드들을 Set에 넣어주면서 indexSet(첫째 줄 배열)이랑 valueSet(두번째 줄 배열)에 값들을 비교하면서 하려고 했는데 빛 좋은 개살구 마냥 아이디어만 좋았지 실제적으로 제 머리가 그걸 구현할 정도로 호환이 안되더군요.. 다음번에 다시 도전해서 올리겠습니다. 그냥 함수 재귀를 이용해서 풀었습니다. 여기에서 통과 조건은..