백준

[백준, Java] 16928번 : 뱀과 사다리 게임

🔗 문제 링크 https://www.acmicpc.net/problem/16928 😮 문제 해결 방법 주사위를 조작할 수 있다고 문제에서 제시했기 때문에 매 위치마다 1~6번까지의 주사위를 던진 후 위치를 담은 Node 객체에 다음 위치와 다음 거리(주사위 던진 개수)를 넣어 큐에 넣어주었다. 매 주사위 굴린 후의 위치에서는 뱀과 사다리가 있는 칸인지 먼저 확인한다. 뱀과 사다리가 있는 칸인 경우 주사위를 한번 굴린 것으로 뱀과 사다리를 탄 이후의 칸으로 이동이 가능하기 때문에 뱀과 사다리 탄 이후 칸 거리 배열에 현재까지 위치의 주사위 개수 + 1을 한 값을 넣어준다. 뱀과 사다리가 없는 칸인 경우 주사위 굴린 이후의 칸 거리 배열에 현재 까지의 주사위 개수 + 1 한 값을 넣어준다. 현재 큐의 칸이 ..

[백준, 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 으로 들어온 배열로 다시 돌려놔 줘야 다른 방향에 대해서도 올바르게 탐색이 가능하다. 즉, 매 턴의 게임판의 상태 배열을 깊은 복사를 통해 한 개 더 생성한 후 복사한 배열을 통해 방향을 탐색하고, 방향 탐색을 끝냈을 땐 기존 배열로 다시 초기화 해주었다..