13913번: 숨바꼭질 4 처음에는 Move 클래스 안에 StringBuilder나 StringBuffer를 넣어서 이전의 경로를 복사해서 최종 경로를 찍도록 했는데 시간 초과가 났다. 아무래도 복사 비용과 새 인스턴스 생성하는 비용이 커서 그런 것 같다. 그래서 예전에 봤던 방법을 사용했는데 prev 배열에 직전 경로를 저장하는 방법이다. prev[a] = b 는 a로 가기위해서는 b를 거친다는 의미이다. 이후 아래와 같이 마지막 K부터 시작점 N까지의 경로를 추적해서 출력하면 된다. int index = K; while(index != N){ index = prev[index]; } 방문 처리 위치에 따라 직전 경로가 갱신이 될 수 있기 때문에 방문 처리 위치도 중요하다. static void BFS..
백준
30869번- 빨리 기다리기 백준 아레나 신청해놓고 까먹고 있다가 부랴부랴 기억해서 참가했었다. 한 시간 반정도 남았을 때 도전했는데 처음 봤을 때는 쉽게 생각하고 BFS로 접근했었다. 제출하니까 시간 초과 뜨길래 다익스트라로 방향을 바꿨으나 시간이 없어서 못풀었었다. 그리고 다 풀고 나서 또 조건 제대로 안 읽어서 불가능할 경우 -1을 출력한다는 것을 못봤다. 그리고 나서는 ‘아 혹시 시간 합이 long이라서 그런가?’ 하고 엉뚱한 것만 손보고 있었다. 이것 때문에 한 15분 정도 더 해멨다.. 결국 접근법 자체는 다익스트라가 맞았다. 대신 고려해야할 점이 빨리 기다리기인데 빨리 기다리기를 사용하면 배차간격을 무시하고 바로 탈 수 있다는 점이다. 예시로 바로본다면 ① -> ②로 가는 소요시간은 2시간이..
5639번: 이진 검색 트리 참고 [백준] 5639번: 이진 검색 트리 - JAVA 고쳐야 할 것 코드를 너무 빨리 짜려는 습관 일정 시간 이상 지나면 굳혀진 방향을 수정 고려하기 구현 고민 일단 반복문으로 방향을 잡고 시작했다. 처음에는 current를 설정하고 current.data보다 작으면 current.left에 추가하고 current = current.left와 같이 현재 노드를 재설정해줬다. 그리고 current.data 보다 클 경우 current = current.parent로 부모로 올라가 설정하려 했다. 문제는 이렇게 위로 올라가려면 어디까지 올라가야 할지 설정하기가 어렵다는 점이다. 현재 노드의 왼쪽 서브 트리는 노드의 키값보다 작다는 것을 가지고 설정해보려 했으나 이 경우 root..
4179번: 불! 문제를 꼼꼼히 읽는 습관이 필요하다고 느낀 문제 구현 자체는 BFS를 활용하는 것이라 크게 어렵지 않았는데 문제 조건 체크하는 게 좀 빡셌다. 나를 괴롭혔던 조건은 다음과 같다. J는 입력에서 하나만 주어진다. -> 초반에 지훈이 위치와 불의 위치를 각각 배열에 담아서 Queue에 넘겼는데 하나의 불 밖에 담지 못해 문제가 생겼다. 또한, 불이 없는 경우에도 문제가 생겼는데 while문의 조건을 !.jq.isEmpty()&&!fq.isEmpty()로 설정해서 불이 없을 때도 탈출 불가를 띄웠다. 지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. -> y가 0이거나 x가 0일 때도 가장자리에 해당하기 때문에 탈출이 가능하다. 그리고 좀 어이없게 실수한 부분은 시작하자마자 탈출하면..
