본문 바로가기

전체 글79

[백준 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.
[백준]boj 17070 파이프 옮기기1 접근 방법 1. 갈 수 있는 방향에 대한 인덱스를 2차원 배열에 저장하였습니다. 방향에 대한 이동은 dir 이차원 배열을 이용하여 오른쪽 이동, 아래로 이동, 대각선 이동을 구현하였습니다. 2. 재귀를 진행하면서 현재 방향으로 갈 수 있는 경우에 대해 모든 탐색을 진행하였습니다. 이를 위해 현재 방향에 대해 매개변수로 넘겨줍니다. 구현하며 어려웠던 점 1. 문제 조건을 하나 빼먹었는데, 빈칸이어야 하는 곳에 대한 확인이 없었습니다. 추가 접근 방안 1. dp로도 이 문제를 접근할 수 있습니다. public class Main_17070 { private static int N; private static int[][] maps; private static boolean[][] visited; privat.. 2022. 9. 30.

티스토리툴바