파게로그

문제 링크: 2178번 제목 https://www.acmicpc.net/problem/2178 최단거리를 찾으므로 BFS로 구현하는 것이 유리하며, 방문하는 새로운 칸에는 현재의 칸에 저장된 값보다 1만큼 큰 값을 저장한다. 코드에서는 이용하지 않았지만, maze 배열의 테두리를 0(이동할 수 없는 칸)으로 감싸게 되면 새로 이동할 칸이 maze를 벗어나지 않는지 체크할 필요가 없다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import jav..

문제 링크: 1012번 제목 https://www.acmicpc.net/problem/1012 연결된 노드의 집합의 개수를 구하는 문제이다. 앞선 문제처럼, visited를 선언하지 않고도 0, 1, 2로 구분하는 방식으로 해서 문제를 풀어갈 수도 있다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static int[] drow = {0, 0, 1, -1}; static int[] dcol = {1, -1, 0, 0}; static class Pos { int row; int col; Pos(int row, in..

문제 링크: 2667번 단지번호붙이기 https://www.acmicpc.net/problem/2667 흔히 말하는 섬 개수와, 각 섬의 면적을 구하는 문제이다. 이 문제에서 섬 개수는 단지의 수, 각 섬의 면적은 각 단지의 집의 수를 뜻한다. DFS 함수 진입 후, 해당 칸이 집이 없는 칸이라면 즉 map[row][col] != 1이라면 함수를 빠져나온다. 그렇지 않을 때에는 해당 칸을 '집이 있으며, 방문을 하였음'이라는 의미로 2로 바꾸어준다. 그리고 집이 있는 칸을 방문하였기에 면적을 1만큼 더해준다. 그 후 지도의 범위를 벗어나지 않는, 동서남북 방향의 칸에 대해서 DFS 함수를 호출하고, 호출된 함수가 반환하는 areaSize 값을 호출한 함수의 areaSize에 할당한다. 이렇게 하면 가장 ..

문제 링크: 2606번 바이러스 https://www.acmicpc.net/problem/2606 서로 연결된 노드들의 집합 개수를 구하는 문제이다. 1번 컴퓨터와 네트워크 상에서 직접 연결된 컴퓨터의 수를 구하면 되므로, 모든 탐색을 끝마친 후 visit 배열의 true 개수를 모두 세고, 1번 컴퓨터를 뺀 값을 출력한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = ne..

문제 링크: 1260번 제목 https://www.acmicpc.net/problem/1260 DFS와 BFS를 구현해보는 가장 기초적인 문제이다. 먼저 그래프 문제의 경우 입력부터 신경쓸 필요가 있다. 그래프가 인접 행렬로 주어진 경우와 인접 리스트로 주어진 경우를 나누어 생각해야 한다. 인접 행렬로 주어지는 경우에는 2차원 배열로 받는 것이 일반적이며, 인접 리스트로 주어지는 경우에는 ArrayList[]를 쓰는 편이 좋다. 2중 ArrayList를 사용하게 되면 get과 set을 사용하게 되어 보기에 흉하다(?). 다만 원칙은 2중 ArrayList를 쓰는 것이며, 따라서 컴파일 경고를 피할 수는 없으며 무시할 수는 있다. DFS는 stack을 별도로 만들어두고서 함수를 호출해도 되지만, 재귀적으로..

문제 링크: 2293번 동전 1 https://www.acmicpc.net/problem/2293 dp[k]는 k원을 만드는 경우의 수를 나타낸다. 이 때 coins[0](엄밀히는 동전 중 임의의 한 개)만을 사용한다면, k가 coins[0]의 배수일 때에는 모두 1가지이므로 if k%coins[0]==0 dp[k]=1을 수행한다. 그 후, coins[1:](엄밀히는 처음에 선택한 동전을 제외한 다른 동전들)에 대해서, dp[k] += dp[k-coin]을 수행한다. coin만을 이용해서 만들 수 있는 경우의 수는 이미 dp[k]에 포함되어 있고, dp[k-coin]은 k-coin원에다가 coin을 이용해 coin만큼을 더해서 k를 만드는 경우의 수이므로 이 둘을 더해준다. import java.util..

문제 링크: 1520번 제목 https://www.acmicpc.net/problem/1520 P(i, j)가 (i, j)의 위치에서 출발지까지 가는 경로의 수를 나타낸다고 한다면 이는 다음과 같은 식으로 표현된다. P(i, j) = sum({P(k, l) | (k, l)은 (i, j)와 인접 & (k, l)은 (i, j)보다 고도가 높음}) P(i, j)의 초기값을 -1로 설정해두어서 방문 여부를 표시한다면, (i, j)를 방문한 경우 P(i, j)를 바로 사용하면 되며 이는 다시 계산할 필요가 없다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { ..

문제 링크: 11066번 제목 https://www.acmicpc.net/problem/11066 앞서 행렬의 곱 문제와 유사하다. 부분 문제의 해를 2차원 배열에 저장한다. 다만 여기서는 한 개짜리 파일을 두 개 합칠 때와 그렇지 않을 때의 계산 과정이 달라진다. merge_cost(A, B) = A.size + B.size merge_cost(AB, C) = merge_cost(A, B) + merge_cost(C) + size(AB) + size(C) 이를 고려하여 dp[i][1]과 dp[i][2]를 모두 미리 채운 후 dp 배열을 채워나간다. import java.util.Arrays; import java.util.Collections; import java.util.Scanner; import..