나아가는중

[백준 Baekjoon] 7569번 토마토- JAVA 문제 풀이 상자에 들어 있는 토마토가 모두 익을 때까지 최소 날짜를 출력하는 문제이다. 최소 날짜와 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향을 보고 bfs탐색으로 푸는 문제란 걸 알았다. 3차원 도형으로 복잡해 보이지만, 3차원 배열로 입력받고 토마토가 있는 위치에서 여섯 방향으로 bfs탐색을 하면 쉽게 풀리는 문제이다. 7576번 토마토 문제에서 살짝 업그레이드 된 문제이다. https://dlee0129.tistory.com/202 [백준 Baekjoon] 7576번 토마토- JAVA [백준 Baekjoon] 7576번 토마토- JAVA 문제 풀이 상자에 들어 있는 토마토가 모두 익을 때까지 최소 날짜를 출력하는 문제이다. 최소 날짜와 왼쪽..

[백준 Baekjoon] 7576번 토마토- JAVA 문제 풀이 상자에 들어 있는 토마토가 모두 익을 때까지 최소 날짜를 출력하는 문제이다. 최소 날짜와 왼쪽, 오른쪽, 앞, 뒤 네 방향을 보고 bfs탐색으로 푸는 문제란 걸 알았다. 입력으로 주어진 토마토는 1 익은 토마토, 0 익지 않은 토마토, -1 토마토가 들어있지 않은 칸 이렇게 세 가지 종류이다. bfs탐색으로 탐색해야 하는 칸(cnt)은 M * N (상자의 크기) - 익은 토마토 - 토마토가 들어있지 않은 칸이다. 익은 토마토에서 주변 토마토가 익기 때문에 큐에 모든 익은 토마토를 저장하고 bfs탐색을 한다. bfs 탐색으로 새로 탐색하는 칸은 방문하지 않았으며 토마토가 들어있지 않은 칸으로 새로 토마토가 익는 경우이다. 이 경우 cnt를 감..

[백준 Baekjoon] 15711번 환상의 짝궁- JAVA 문제 풀이 문제의 설명만 보면 정말 간단한 문제처럼 보인다. A, B를 더한 값을 소수 2개로 만들 수 있는지 검사하면 된다. 하지만 제한사항의 A와 B의 최댓값이 2 x 10^12로 매우 커서 일반적인 방법으로는 불가능하다. A와 B의 합이 최대 4 * 10^12로 범위가 매우 큰데 그것의 루트값 2000000으로만 검사해주면 된다.. 합이 4미만의 경우 합이 4미만인 경우 소수 2개로 만드는 방법은 없다. 합이 짝수인 경우 골드바흐의 추축에 의하면 2보다 큰 모든 짝수는 두 개의 소수의 합으로 표시할 수 있다. 합이 홀수인 경우 두 수의 합이 홀수가 되려면 짝수 + 홀수이어야만 한다. 따라서 짝수인 소수 + 홀수인 소수로 동일한 합을 만들 ..

백준 Baekjoon 18870번 좌표 압축 - JAVA 문제 풀이 주어진 입력 값들을 정렬했을 때 몇번째 순서인지 출력하는 문제이다. 입력 배열은 후에 다시 사용되어 새로운 배열에 복사한 다음 정렬한다. Map 을 사용하여 0부터 좌표의 순서를 저장한다. 중복되는 좌표값들이 있기 때문에 Map을 사용한다. 입력 값들을 Map에서 찾으면 그 순서를 알 수 있다. 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.HashMap; import java.util.Map; import java.util.Strin..

백준 Baekjoon 1504번 특정한 최단 경로 - JAVA 문제 풀이 1 -> v1 -> v2 -> N 1 -> v2 -> v1 -> N 위의 두 가지 방법 중에 최단거리로 N까지 가는 방법을 구하는 문제이다. 다익스트라 알고리즘을 사용하여 각 이동(예, 1->v1, v1->v2, 1->v2)의 최단거리를 구하고, 두 가지 방법 중에 최단 경로를 출력하면 된다. 각 이동에 대해 다익스트라를 사용하여 총 6번 해도 되지만, 편의상 1, v1, v2에서의 모든 정점과의 최단거리를 구하여 사용하였다. min[0] = 1에서 모든 정점의 거리 min[1] = v1에서 모든 정점의 거리 min[2] = v2에서 모든 정점의 거리이다. 두 방법의 최단경로는 아래의 값을 비교해주어 구한다. min[0][v1](1..

백준 Baekjoon 1238번 파티 - JAVA 문제 풀이 다익스트라 알고리즘을 사용하여 푸는 문제이다. 주로 양방향 그래프가 주어지고 다익스트라 알고리즘을 활용하여 푸는 문제들이 나왔는데, 이번에는 단방향 그래프가 주어졌다. 모든 마을에서 다익스트라를 사용하여 최단거리를 구하는 방법도 존재하지만, X를 출발지로 지정하면 다익스트라 알고리즘을 두번만 사용하여 구할 수 있다. 정방향과 역방향 그래프와 각각의 최단 거리를 저장할 배열이 필요하다. 주어진 단방향 그래프를 그대로 입력받고 다익스트라를 사용하면 모든 마을에서 X까지의 최단거리를 구할 수 있다. 하지만 반대로 X에서 마을로 돌아오는 길을 구하기 위해서는 입력 받는 그래프를 역으로 바꿔 저장한 다음 다익스트라를 사용하여 구해야 한다. 소스 코드 i..

백준 Baekjoon 2616번 소형기관차 - JAVA 문제 풀이 다이나믹 프로그래밍과 누적합을 사용하여 푸는 문제이다. 제한사항의 기관차의 수가 그리 크지 않어 dfs탐색으로도 풀 수는 있을거 같지만, 시간이 오래걸리고 문제에서 원하는 풀이 방식은 아닌듯 했다. 누적합을 사용하여 뒤에 DP에서 기관차가 끌 수 있는 최대 객차의 수의 승객의 합을 쉽게 구할 수 있다. DP의 점화식은 다음과 같다. dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j - max] + sum[j] - sum[j - max]) i를 1 ~ 3 범위로 증가 시키며 각 숫자의 기관차가 운송할 수 있는 최대의 손님 수를 구한다. j를 i * max의 범위부터 시작하는데, 예시로 주어진 문제를 예로 들어..

백준 Baekjoon 16954번 움직이는 미로 탈출 - JAVA 문제 풀이 BFS탐색을 사용하여 캐릭터를 이동 시킨다. 최초에는 처음 시작위치인 7,0을 넣고 시뮬레이션을 시작한다. 큐에서 캐릭터를 현재 케릭터들의 위치들을 꺼내와 9방향으로 이동할 수 있는지 검사하고 새로운 위치를 큐에 추가한다. 큐의 사이즈만큼만 반복하여 큐에서 캐릭터를 꺼내면 새로 추가되는 위치는 탐색하지 않게 된다. 동일한 위치에 여러 캐릭터가 이동하는 것을 방지하기 위해 visit배열을 둔다. visit배열은 매 턴이 끝날때 마다 새로 생성되어야 한다. 이전에 있었던 위치로 돌아가야 하는 상황도 존재한다. 새로운 위치로 이동시켜 큐에 추가한 위치가 벽이 이동하면서 벽과 겹쳐질 수 있어 큐에서 꺼냈을 때 검사해야 한다. 케릭터 이..

[백준 Baekjoon] 14719번 빗물 - JAVA 문제 풀이 특별한 알고리즘의 사용은 없는 구현을 사용한 문제이다. 빗물이 고이는 두가지 경우를 생각하여 각각 구해줌으로 문제를 풀었다. 1 왼쪽 기둥보다 오른쪽의 기둥이 큰 경우. 좌에서 우로 순회한다. 1.1 왼쪽 기둥의 높이를 h, 위치를 left에 저장하였다. 1.2 왼쪽 기둥보다 오른쪽 기둥이 큰거나 같은 경우 양 기둥 사이를 순회하며 두 기둥중 작은 기둥의 높이에서 뺄셈을 한다. 1.3 왼쪽 기둥과 위치를 새로 최신화 해준다. 2 왼쪽 기둥보다 오른쪽의 기둥이 작은 경우. 우에서 좌로 1에서 구한 마지막 왼쪽 기둥까지 순회한다. 2.1 1에서 구한 마지막 왼쪽 기둥까지의 빗물을 계산이 완료되어 마지막 왼쪽 기둥까지만 한다. 2.2 오른쪽 기..

** 백준 Baekjoon 16974번 서울 지하철 2호선 - JAVA 문제 풀이 주어진 입력으로 그래프를 만들었을 때, 순환선(사이클)과의 거리를 각 역마다 출력하는 문제이다. 그래프에서 사이클을 찾는 것이 가장 중요하다. 사이클을 찾고 사이클에서 각 역이 얼마나 떨어져 있는지 찾아 문제를 해결하였다. 사이클을 찾는 여러 방법이 있을것이다. 각 역마다 사이클을 점검하는 방법을 처음 생각하였는데 그러면 비용이 클것 같아 한번에 사이클을 찾는 방법에 대해 생각해보았다. 빽트래킹과 유사하게 스택을 사용하여 문제를 해결하였다. 각 역을 방문할 때에 스택에 추가한다. 방금 전 방문한 곳이 아니며 이전에 방문한 경우 사이클이 발생한다. 스택에 사이클의 시작점을 추가한다. 사이클을 체크할때 해당 역이 다시 나올때까..