JUINTINATION

문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 문제로 깊이우선탐색과 너비우선탐색의 개념을 익히는 문제입니다. 코드 자바 import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; i..

문제 https://www.acmicpc.net/problem/16938 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 풀이 이 문제에서의 알고리즘 캠프를 여는 기준은 다음과 같습니다. 문제는 2문제 이상이어야 한다. 난이도의 합은 L 이상, R 이하여야 한다. 가장 어려운 문제와 가장 쉬운 문제의 난이도 차이는 X 이상이어야 한다. 캠프에 사용할 문제를 고르는 경우의 수를 구해야 하는 문제이며 dfs를 이용하여 해결하였습니다. 코드 C언어 모든 입력을 받은 후에 qsort 함수를 이용하여 각 문제의 난이도가 담긴 정수 배열 arr를 정렬한 후에 dfs 함수를 실행합니다. 이때 함수의 매개변수는 처음부터 탐색하기 위해 i..

문제 https://www.acmicpc.net/problem/16936 16936번: 나3곱2 나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다. 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 www.acmicpc.net 풀이 정수 x가 있을 때 다음과 같은 2개의 연산을 N-1번 적용하는 게임을 이용하여 만든 수열 a를 섞은 수열 b를 입력받고 a를 구하는 문제입니다. 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 한다. 곱2: x에 2를 곱한다. 코드 C언어 먼저 수열 b를 qsort를 이용하여 오름차순으로 정렬합니다. 방문 여부를 확인해주는 bool형 정수 배열 visited..

문제 https://www.acmicpc.net/problem/16945 16945번: 매직 스퀘어로 변경하기 1부터 N2까지의 수가 하나씩 채워져 있는 크기가 N×N인 배열이 있고, 이 배열의 모든 행, 열, 길이가 N인 대각선의 합이 모두 같을 때, 매직 스퀘어라고 한다. 크기가 3×3인 배열 A가 주어졌을 때, www.acmicpc.net 풀이 크기가 3 × 3인 배열을 1부터 9까지의 수가 1개씩 들어있고 모든 행, 열, 대각선의 합이 모두 같은 매직 스퀘어로 변경하려고 합니다. 한 칸에 있는 수 a를 b로 변경하는 비용은 |a - b|일 때 매직 스퀘어로 변경하는 최소 비용을 구해야 합니다. 코드 C언어 지난번에 작성했던 스도쿠 문제와 비슷합니다. 배열의 크기는 3 x 3으로 크지 않기 때문에 ..

문제 https://www.acmicpc.net/problem/4574 4574번: 스도미노쿠 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 채워져 있는 도미노의 개수 N이 주어진다. (10 ≤ N ≤ 35) 다음 N개 줄에는 도미노 하나를 나타내는 U LU V LV가 www.acmicpc.net 풀이 스도미노쿠는 스도쿠와 도미노를 혼합한 게임으로 9 x 9 크기의 보드에 1부터 9까지 숫자가 1개씩 쓰여져 있고, 나머지 72칸은 도미노 타일 36개로 채워야 합니다. 도미노 타일은 1부터 9까지 서로 다른 숫자의 쌍(1+2, 1+3, 1+4, 1+5, 1+6, 1+7, 1+8, 1+9, 2+3, 2+4, 2+5, ... , 8 + 9)이 모두 포함되어 있습니다. 이때 ..

문제 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 풀이 스도쿠 규칙에 맞춰 9 x 9 크기의 보드를 채우는 문제입니다. dfs를 이용하여 모든 칸에 대해 어떤 숫자가 해당 칸에 들어갈 수 있는지에 대한 여부를 sudoku 함수를 통해 확인받아가며 2차원 정수 배열에 기록하는 방식을 사용했습니다. 코드 C언어 2차원 정수 배열 arr로 9 x 9 크기의 보드를 표현합니다. dfs 함수에서 보드의 (x, y)의 위치에 있는 숫자를 arr[y][..