문제 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 현재 사람이 인출하는데 필요한 시간은 앞으로 인출할 사람들이 기다려야하는 시간이다. 그러므로 총 시간은 시간이 적게 걸리는 사람이 먼저 인출할 때 최소가 된다. 입력받은 배열을 오름차순으로 정렬하는 것이 이 문제에서 사용되는 그리디 알고리즘이다. for문을 통해 현재 사용되는 시간 $\times$ 남은 사람의 수를 합한 값을 출력한다. 코드 import java.util.* fun main() { val br = System.`in`.bufferedReader() val bw = S..

문제 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 풀이 이러한 문제들의 graph는 2차원 ArrayList로 만들 수 있다. 연결되어 있는 컴퓨터 번호 쌍을 각각의 ArrayList에 추가해준다. 1번 컴퓨터와 연결되어있는 컴퓨터들을 찾는 문제로 1번 컴퓨터부터 시작하는 BFS와 DFS로 해결하는 문제이다. BFS로 해결하는 경우 Queue를 이용한다. 큐에서 꺼낸 ArrayList에 연결되어있는 번호가 방문한 적이 없다면, 그 번호로 시작하는 ArrayList를 queue에 추가해주고 cnt는 +1 해준다...

문제 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 풀이 재귀로 구현한 DFS와 큐로 구현한 BFS로 해결할 수 있다. 영역과 영역의 크기는 mutableList를 이용해 저장해주었다. graph는 false로 초기화 되어있는 BooleanArray를 이용했다. 입력받은 직사각형이 지나는 좌표는 true로 바꾸어준다. 이때 주어진 좌표의 기준점이 왼쪽 위(graph[0][0])가 아니라 아래(graph[rows][0])인 것을 주의해서 for문을 만들어 주어야한다. graph를 순회하며 ..

문제 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 재귀로 구현한 DFS와 큐로 구현한 BFS로 해결할 수 있다. 단지와 집의 수는 mutableList를 이용해 저장해주었다. 주어진 graph를 순회하며 방문한적이 없고 graph가 1인 경우 단지를 추가하고 DFS나 BFS를 호출한다. DFS의 경우에는 graph가 방문하지않고 1인 경우에 다시 DFS함수를 호출해주고, 호출될 때 마다 집의 수를 1 증가시킨다. BFS의 경우에는 해당하는 경우에 Queue에 추가해주고 집의 수를 1 증가시킨다. 리스트..

문제 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 입력받은 그래프를 너비 우선 탐색(BFS)을 이용해 풀이하면 된다. BFS로 풀이할 때, 일반적으로는 graph와 같은 크기로 Boolean 배열인 visited를 만들고 방문 체크를 해준다. 그렇지만 이번 문제에서는 visited를 사용하지 않았고, graph[x][y]가 1일 때만 graph[x][y]를 갱신해주는 방법을 이용하였다. graph[x][y]가 0인 경우(벽)와 1 이상인 경우(이미 방문함)에는 방문하지 않기 때문에 최단거리를 알 수 있다. 코드 import java..