Algorithm/BOJ45 [백준] 2206번 벽 부수고 이동하기 자바 문제 (BFS, 골드4) 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 풀이 나에겐 이해하기 너무 어려운 문제였다... 일단 이 문제에서 궁금했던 세 가지는 1. 격자 최단경로에서 BFS를 쓰는 이유? : 트리의 경우, DFS로 두 정점 간의 거리를 구할 수 있다. BUT, 트리(거리가 하나 존재)라는 확증이 필요하다. 그래프의 경우, 내가 구한 경로가 최단경로인지 확신할 수 없다. 그래프를 DFS탐색할 경우 한 정점에 대해 타고타고 내려간 경로가 최소인지 확인이 필요하다. 따.. 2022. 1. 24. [백준] 10974번 모든 순열 자바 문제 (실버3) 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 ✔️ 사용 변수 문제에서 주어지는 순열 출력 숫자 : int N 출력 순서를 늘려나갈 숫자 변수: int depth 하나의 경우를 담아 출력할 배열 : int[] result 해당 숫자를 사용했는지 여부를 체크하기 위한 배열: boolean[] visited ✔️permutaion알고리즘 - 아래 그림처럼 각각의 시작 숫자로 사용하지 않은 숫자로 result배열을 채워나가면서 계속해서 재귀 호출한다. - 한 번의 수행 후에(마지막 배열의 호출이 끝난 후) 다시 visited배열을 초기화해가면서 사전 순으로 수를 담는다. 소스 .. 2022. 1. 21. [백준] 2573번 빙산 자바 문제 (골드4) 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제 풀이 ✔️ 사용변수 빙산의 높이를 입력받을 2차원 배열: int[][] ice 1년 녹는 빙산의 개수를 받을 2차원 배열: int[][] melt 빙산이 분리되는 것을 확인하기 위해 DFS를 실행할 2차원 배열: boolean[][] visited 반복하며 상하좌우로 움직이기 위한 1차원 배열: int[] moveX, int[] moveY ✔️ afterYear() 알고리즘 1. ice배열을 순회하며 0이상의 값을 가진 경우(빙산 존재.. 2022. 1. 10. [백준] 1987번 알파벳 자바 문제 (골드4) 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 풀이 문제보고 바로 DFS문제라고 생각했고, visted배열을 받아 방문 여부를 표시하며 알파벳 방문 최대값을 구하면 될 것이라고 생각하고 풀었다. 그리고 방문 알파벳은 ArrayList에 담아서 contains()함수 사용해서 구별하려고 했는데, DFS실행 시, 방문했다가 나온 알파벳을 다시 지우기가 힘들었다. remove함수에서 계속 오류가 발생했다. (왜그런지 아직도 모르겠음ㅠ) 구글링해보니까 알파벳 개수만큼 boolean배열을.. 2022. 1. 3. [백준] 11399번 ATM 자바 문제 (실버3) 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 풀이 처음에 순열 함수를 따로 만들어서 모든 순열 경우의 수를 구해서 그 합을 구해 작은 값을 찾아가는 식으로 풀었다. public static void permutation(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) { if(depth == r) { int sum = 0; for(int i = 0; i < r; i++) for(int j = 0; j 2022. 1. 3. [백준] 1753번 최단경로 자바 문제 (골드5, 다익스트라 알고리즘) 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제풀이 처음에 다익스트라 알고리즘인 줄 모르고 DFS로 풀었다. 정점과 가중치 값을 ' , '로 연결하여 ArrayList에 String값을 담아서 도착 정점까지의 가중치합을 합하여 weight배열에 담아줬었다. 도착정점까지 가는 모든 가중치합을 비교하며 weight배열을 갱신하고 마지막에 출력해줬다. 이렇게... public class Main { static int[] weight;.. 2021. 12. 7. 이전 1 ··· 4 5 6 7 8 다음
