본문 바로가기

Algorithm43

[백준 BOJ] 1149번 RGB 거리(자바/DP) 접근 방법 1. 조건에 따라 모든 집은 이웃의 색과 달라야 합니다. 2. 모든 칠해지는 경우의 수를 찾기 - 현재 빨간색으로 칠할 때 이전 집은 초록이거나 파랑이어야 합니다. - 현재 파란색으로 칠하는 경우 이전 집은 빨간색이거나 초록이어야 합니다. - 현재 초록색으로 칠하는 경우 이전 집은 빨간색이거나 파란색이어야 합니다. 따라서, 현재 색을 칠하기 위해서는 그 전 색깔 중에서 최소를 선택하면 됩니다. 현재 빨간 색을 칠하는 경우 이전 집은 초록이거나 파랑이어야하며 초록과 파랑 중 최소 비용을 선택하면 됩니다. 주의할 점 1. 처음으로 생각한 아이디어는 매번 최소 비용을 선택하는 방법입니다. 하지만, 이런 경우 이전 집까지의 최소 비용이 현재의 최소 비용을 보장하지는 않습니다. 따라서, 모든 칠해지는 .. 2022. 10. 17.
[백준 BOJ] 17472 다리 만들기2(MST, BFS) - 자바 문제 접근 방법 1. 먼저 각 섬들에 대해 번호를 부여해줍니다. (BFS) 저는 인접한 섬들에 대해 같은 번호를 부여하도록 하였습니다. 2. 다리 놓기(이중 for문) 각 섬들 사이의 거리를 구하기 위해 저는 모든 행과 열을 탐색하였습니다. 섬과 섬 사이의 0의 개수를 카운트한 다음 이에 대해 Math.min을 통해 최소 다리 길이를 구하였습니다. 3. 모든 섬을 연결하는 다리 길이의 최솟값 구하기(MST - 크루스칼 알고리즘) 각 섬에 대한 최소 다리 길이를 구했다면, 이제 모든 섬을 연결할 수 있는지 확인해야 합니다. 특히 이때 MST 알고리즘 중에서 저는 크루스칼 알고리즘을 사용하였습니다. 또한, 최소 길이를 구하는 것이기 때문에 우선 순위 큐를 통해 다리 길이가 작은 순서대로 정렬시켰습니다. 우선.. 2022. 10. 10.
[BOJ 백준] 14502 연구소 - 자바 문제 접근 방법 1. 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갑니다. 이 조건을 토대로 저는 BFS라는 접근 방법을 떠올릴 수 있었습니다. 2. 벽의 개수는 3개이며, 꼭 3개를 세워야 합니다. 이 조건을 토대로 저는 놓을 수 있는 벽의 위치를 찾는 메서드 choiceLocation 함수를 구현하였습니다. 벽의 위치를 세울 수 있는 모든 위치의 경우의 수를 int[][] output에 인덱스 형태로 저장하였습니다. 문제 접근하며 어려웠던 점 1. 벽을 놓을 수 있는 3개의 위치를 지정하면 그때 BFS 함수를 호출하는 로직을 구현하는 과정에서 다른 경우의 수도 계산하기 위해서 초기화가 이루어져야 했습니다. 따라서, 저는 배열의 복사본을 만들어 복사본으로 bfs를 탐색하였습니다. public cl.. 2022. 10. 6.
[SWEA] 자바 1249. [S/W 문제해결 응용] 4일차 - 보급로 접근 방법 1. BFS로 접근하였습니다. 경로에 대해 저장할 이차원 배열 int[][] sum을 선언하여 이미 방문한 경로인 경우에는 현재 방문할 예정인 경로와 이미 방문한 경로의 값을 비교해 현재 방문할 예정인 경로가 더 작은 경우 큐에 다시 넣어주었습니다. 2. 특히, 이 문제의 경우 그냥 큐를 사용하였더니 시간초과가 났습니다. 따라서, 우선순위 큐를 통해 작은 값들을 먼저 돌게 하여 시간 초과 문제를 해결할 수 있었습니다. 구현 설명 1. class Point에는 x,y 좌표와 현재 경로에 대한 합을 저장하기 위한 value를 선언하였습니다. 2. int[][] dir = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}} 의 경우 기존에 상하좌우로 진행하였던 방향과는 다르게 좌우상하로 .. 2022. 10. 2.

티스토리툴바