Algorithm

[백준, Java] 1967번 : 트리의 지름

🔗 문제 링크 https://www.acmicpc.net/problem/1967 😮 문제 해결 방법 Map을 이용해 트리를 만들어 준다. 문제에서 루트노드가 1이라고 주어졌기 때문에 루트 노드를 이용해 가장 멀리 있는 노드를 먼저 탐색한다. 가장 먼 노드를 찾았다면, 해당 노드로 다시 가장 먼 노드를 탐색하면 노드와 노드간 가장 먼 지름이 탐색된다. 루트 노드를 이용해 DFS 탐색 및 가장 먼 노드 찾기 탐색한 가장 먼 노드를 이용해 다시 한번 DFS 탐색 및 지름 갱신 🚩 Java 코드 package com.algorithm.Baekjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReade..

[백준, Java] 1068번 : 트리

🔗 문제 링크 https://www.acmicpc.net/problem/1068 😮 문제 해결 방법 Map을 이용해 구현에 필요한 트리를 만들어 준 후 DFS를 이용해 루트 노드부터 탐색한다. Map에서 현재 노드에 해당하는 리스트가 없는 경우는 단말 노드이기 때문에 단말 노드 카운트를 증가시킨다. 현재 노드가 삭제할 노드인 경우는 다음 노드들은 모두 삭제 되므로 그대로 return한다. 만약 현재 노드에서 연결된 자식 노드가 삭제되는 노드이면서 단말 노드인 경우는 삭제 후 현재 노드가 단말노드가 되기 때문에 단말 노드 카운트를 증가시킨다. 🚩 Java 코드 package com.algorithm.Baekjoon; import java.io.BufferedReader; import java.io.IOEx..

[백준, Java] 2573번 : 빙산

🔗 문제 링크 https://www.acmicpc.net/problem/2573 😮 문제 해결 방법 빙산을 녹여야 하는지 판단을 하는 배열과 실제로 인접한 바다를 체크한 후 녹은 후의 빙산 상태를 저장하는 배열 두개를 사용해서 해결했다. 빙산 상태를 녹이는 배열은 현재 해의 빙산 배열을 복사한 배열이다. 기존 빙산 배열을 녹은 후 빙산 상태를 저장하는 배열로 사용하기 위해 복사한다. 기존 빙산 배열을 이용해서 빙산이 남아있고, 상하좌우 인접한 부분에 바다가 있는지 판단한다. 이 때, 단 하나로 빙산이 남아있지 않았다면, 빙산이 다 녹을때 까지 두 덩어리 이상으로 빙산이 나눠지지 않았기 때문에 0을 리턴하고 종료한다. 상하좌우 인접한 바다의 개수 만큼 빙산의 크기를 녹여준다. 현재 해의 녹일 수 있는 빙산..

[백준, Java] 12100번 : 2048(easy)

🔗 문제 링크 https://www.acmicpc.net/problem/12100 😮 문제 해결 방법 첫 번째 턴부터 시작해서 5턴이 넘어갔을 때 남아있는 블럭 중 최대 크기의 블럭을 탐색했다. 매 턴마다 상, 하, 좌, 우 방향으로 블록이 이동하면서 합쳐질 수 있고, 합쳐진 이후에는 해당 방향으로 블록들을 밀어줘야한다. 그리고, 한 턴당 상, 하, 좌, 우 방향으로 블록을 옮기기 때문에 각 방향으로 블록을 옮길 때마다 블록의 배열을 매 턴의 input 으로 들어온 배열로 다시 돌려놔 줘야 다른 방향에 대해서도 올바르게 탐색이 가능하다. 즉, 매 턴의 게임판의 상태 배열을 깊은 복사를 통해 한 개 더 생성한 후 복사한 배열을 통해 방향을 탐색하고, 방향 탐색을 끝냈을 땐 기존 배열로 다시 초기화 해주었다..

[프로그래머스, Java] 빛의 경로 사이클

🔗 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/86052 🤔 문제 각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다. 빛이 "S"가 써진 칸에 도달한 경우, 직진합니다. 빛이 "L"이 써진 칸에 도달한 경우, 좌회전을 합니다. 빛이 "R"이 써진 칸에 도달한 경우, 우회전을 합니다. 빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옵니다. 예를 들어, 빛이 1행에서 행이 줄어드는 방향으로 이동할 경우, 같은 열의 반대쪽 끝 행으로 다시 돌아옵니다. 당신은 이 격자 내에서 빛이 이동할 수 있는 경로 사이클이 몇 개 있고, 각 사이클의..