쫑쫑이의 블로그

https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 구현 문제이므로, 시키는대로 하면 된다!!! 문자를 전부 숫자로 바꿔서 배열을 만들었고, 마지막에 키를 받을 때 97씩 빼서 0 부터 26 사이의 가진 키들의 배열을 만들어줬다 42는 벽, 46은 빈 공간이다 모서리 순회하면서 조건에 만족하면 bfs로 탐색한다 42이거나 방문 했으면 리턴 1) 46이면 bfs 큐에 추가 (코드 내부에는 판별하는 조건문 없음) 2) 97보다 크면 키 추가하고 bfs 큐에 추가하..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 입력을 받고 B는 가중치를 주면서 A의 다음에 나올 수 있는 배열에 추가한다 학생들 중에서 가중치가 0인 인덱스를 큐에 넣고 큐에서 하나씩 빼면서 다음에 나올 수 있는 배열 반복문으로 돌면서 가중치 빼주고 가중치 0인 인덱스를 큐에 넣는 것을 반복한다 import java.io.*; import java.util.*; public class Main { ..

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..