문제 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출..

문제 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 풀이 이 문제는 Traveling Salesman problem(TSP)라고 불리는 외판원 순회 문제 유형의 가장 기본적인 형태이다. DFS로 풀이하면 된다. 한 도시에서 모든 도시를 방문했을 때, 출발지로 다시 돌아올 수 있다면 총 비용을 현재까지의 최솟값과 비교하여 저장하는 방식이다. 모든 도시를 한 번씩 출발지로 하여 dfs()를 호출하면 된다. 코드 import java.util.* import kotlin..

문제 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 풀이 각각의 테스트 케이스마다 입력받은 graph를 DFS, BFS로 탐색한 결과를 출력해주면 된다. graph는 false로 초기화되어 있는 BooleanArray를 선언한다. 입력받은 좌표는 true로 바꿔준다. for문을 통해 graph의 좌표가 true이면 DFS, BFS 함수를 실행해주고 cnt를 +1 해준다. 이후 cnt를 출력해주면 된다. 코드 - BFS import java.util.* data class Point(val x: Int, val y: In..

문제 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를 순회하며 ..