쫑쫑이의 블로그

https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 각 행과 열, 3x3 사각형의 방문 배열을 만들어 1 ~ 9 까지 중복없이 스도쿠 퍼즐을 채운다 3x3 사각형의 방문 배열의 경우 왼쪽 위에서부터 순서대로 배정했고, 행을 3으로 나눈 몫에 3을 곱하고, 열을 3으로 나눈 몫을 더해주면 해당 인덱스에 접근할 수 있다 사전식에서 가장 앞서는 경우를 출력해야하기 때문에 각 자리를 1부터 9까지 가능한 경우의 수를 구하고 끝까지 구해질 경우 탈출조..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 알파벳을 아스키코드로 바꿔서 65씩 빼주면 0 ~ 25 사이의 숫자로 표현 가능하다 크기가 26인 방문 배열을 만들어 알파벳 방문체크해가면서 dfs로 탐색하면 된다 import java.awt.*; import java.io.*; import java.util.*; public class Main { static int count, X, Y; static boolean[] vtd; stat..

https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 예제 입력 값이 2개씩(전봇대A, 전봇대B)인데 전봇대 A 기준으로 정렬하여 전봇대 B로 가장 긴 증가하는 수열을 만들고 인덱스 별 만들 수 있는 수열의 크기를 구하고 뒤에서부터 size가 처음 나온 위치를 제외한 모든 위치의 전봇대 A값을 출력한다 예제를 예시로 들어 전봇대 A를 기준으로 정렬을 하면 [1,8], [2,2], [3,9], [4,1], [6,4], [7,6], [9,7], [1..

https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 최소 스패닝 트리 문제이다 아무 생각없이 프림을 사용해서 풀었는데 풀고보니 크루스칼으로 푸는게 좋아보인다 N x N 행렬을 만들고 피타고라스의 정의 a^2 + b^2 = c^2를 활용해 두 변 사이의 거리를 구해 넣어줬다 우선순위큐에서 거리를 기준으로 최소값을 꺼내 방문 하지 않은 노드들을 방문해가면서 결과값에 더해줬다 출력은 10^-2까지만 구하면 된다 import java.io.*; import..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 위상정렬과 우선순위큐를 사용해서 풀이하면 된다 입력 값에 맞게 가중치를 추가해주고 1부터 N까지 가중치가 0인 값만 우선순위큐에 넣어준 후 우선순위큐에서 하나씩 꺼내면서 출력값에 추가하고 꺼낸 값이 방문할 수 있는 문제 번호의 가중치를 감소하고 가중치가 0이 되면 우선순위큐에 넣는 과정을 반복한다 import java.io.*; import java.util.*; p..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 위상정렬을 사용해서 풀이하는데 가중치를 줄일 때마다 건설시간 누적값을 저장한 배열을 비교해줘야한다 각 노드 별 가중치는 0 1 1 2가 되고, 건설시간 누적값은 모두 0으로 초기화 해둔다 2가 완료될 때 건설시간 누적값 11(10 + 1)을 4의 건설시간 누적값 0과 비교해서 최대값 11을 넣고 3이 완료될 때 건설시간 누적값 110(10 + 100)을 4의 건설시간 누적값 11과 비교해서 ..