자세한 풀이: 주석 참고 두 구획에 따른 가중치의 차이는 없으므로 부분집합의 원소의 수가 1이상 n/2 이하인 조합을 고른다. 고른 조합 두개가 나오면, 각각의 조합(red, blue) 에 대해 union-find를 진행한다. 이때 같은 색에 포함되며 인접해있다면 union을 진행한다. 모든 union이 완료되면 각 노드에 대해 탐색을 진행한다. 1. 모두 방문할 수 있는지, 2. 방문했을 때 색이 같다면(union 되어있다면) 같은 부모에 포함되었는지 검사한다. package com; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public cla..

입력 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다. 출력 영상을 압축한 결과를 출력한다. 예제 입력 1 복사 8 11110000 11110000 00011100 00011100 11110000 11110000 11110011 11110011 예제 출력 1 복사 ((110(0101))(0010)1(0001)) 해설 size가 2가 될때까지 분할정복을 진행한다. 2가 되었다면 네칸의 합이 4인 경우와 0인 경우는 각각 모든 수가 같은 경우이다. 4또는 0이 아닌 경우는 네칸의 수가 다른 ..

문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다. 출력 ..

풀이 c++ 에선 pair형이더라도 pq에서 pair first, second순으로 정렬이 되는데에 반해, 자바는 그렇지 않다. 따라서 1. Pair class를 선언해 Pair를 정렬할 수 있는 compareTo를 오버라이딩 2. 오름차순 정렬이 되도록 compareTo를 오버라이딩 하였다. 장점으로, 음수화하여 정렬했다가 다시 꺼낼 때 양수화하는 과정이 없어서 코드 작성자의 의도에 맞는 코드를 짤 수 있어 조금이나마 가독성이 좋아졌다고 생각한다. 코드 import java.io.*; import java.lang.reflect.Parameter; import java.util.*; public class Main { static class Pair implements Comparable { int c..

https://www.acmicpc.net/problem/16935 16935번: 배열 돌리기 3 크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다. 1번 연산은 배열을 상하 반전시키는 연산이다. 1 6 2 9 8 4 → 4 2 9 3 1 8 7 2 6 9 8 2 → 9 2 3 6 1 5 1 8 3 4 2 9 → www.acmicpc.net 와우 진짜 너무 빡세서 나의 ADHD와의 싸움을 또 해냈다. 각 cmd (명령어 == 커맨드) 별로 함수를 하나씩 만들고 실행하도록 했다. 90도 회전의 경우 가로길이와 세로길이가 서로 바뀌기 때문에, 명령어 실행 중에 복잡해지는 것을 피하기 위해 얕은 복사로 2차원 배열이 계속 반환될 수 있게 했다. 그리고 cmd함수의..

꼼꼼하게 구현이 필요한 문제이다. 현재 입력된 cur를 visit에 체크하여 visit 2차원배열의 값을 1로 바꾼다 그리고 각각 우상대각, 좌상대각, row, column의 개수를 세는 변수를 생성한다. 2중 반복문을 돌려 visit의 합이 5라면, 한줄의 빙고가 완성된 것이다. 우상대각, 좌상대각, row, column의 개수가 3이 되었다면 현재 위치를 출력하고 종료한다. 코드의 아래 주석은 질문 게시판에 있던 반례이다. 이 반례로 내가 현재 출력값을 다른걸로 착각하고 있었음을 깨달았다. package com.boj.s2578; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; imp..

3584번: 가장 가까운 공통 조상 해결 트리의 노드는 모두 root node를 부모로 한다. 즉, 모든 노드가 연결되어있다. 따라서 각 노드의 부모 노드를 찾다보면 root node에서 만날 것이다. 💡 다르게 말하자면 트리는 내 부모노드와 내가 공통 조상을 가지고 있다. 트리 구조 저장 x, y의 레벨을 찾고 부모 노드를 저장하는 방법은 union-find 알고리즘에서 root Parent를 찾는 방법에서 아이디어를 떠올려 풀었다. union-find 알고리즘의 disjoint set에서 서로 다른 두 노드가 연결되었는지 알기 위해, Parent 배열이 존재하고, 두 노드가 연결될 경우 두 노드의 부모를 같게 한다. getParent라는 재귀함수를 통해 두 노드의 부모가 같다면 연결되었다고 판단한다...

재귀함수로, ___를 두가지 방식으로 해결할 수 있다. 재귀 횟수를 세는 n, 그리고 ___ 을 세는 cnt가 있다 재귀 횟수는 n번으로 n이 1보다 작거나 같으면 종료해야한다. cnt는 ___을 세기 위함이다. n을 감소시켰기 때문에 증가하는 변수인 cnt를 0으로 초기화하였다. cnt는 맨 처음 컴공과 학생이 교수에게 하는 말인 "재귀함수가 뭔가요./ " 앞에는 없으므로 0이 초깃값이다. (사실 종료 조건을 n으로 둔 다음 인자에 cnt만 두고 cnt를 증가시켜 종료 조건을 달면 함수 파라미터 수가 하나 줄어서 깔끔했을 것 같다) 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanne..

12851번: 숨바꼭질 2 해결 BFS 로 해결했다. 숨바꼭질 1 과 다른 점은, queue에 넣기전 방문체크하지 않는다는 것이다. 물론 숨바꼭질 1도 queue에 넣은 후 pop하고 나서 방문체크해도 옳은 답이 나온다. 어차피 현재 위치가 동생 위치 k일 때, bfs탐색을 거쳤으므로 제일 처음 종료조건 k에 도달한 상태가 최적의 답(최소시간)이기 때문이고, 바로 return하기 때문에 방문체크 순서는 상관없기 때문에 그런 것이다. 단지 queue에 넣기 전 방문체크 하는 것이 불필요하게 q에 넣는 것을 줄일 수 있기 때문에 그렇게 하는 것이다. 그러나 숨바꼭질 2에서는 queue에 넣기 전 방문체크를 하면, 동일한 위치에는 다시 방문하지 않게 되므로 1→ 1 +1 → 2 2 1 → 12 → 2*2 인 ..

매 칸에 대해서 방문 검사를 하며, 해당 칸이 울타리 안쪽이라면 bfs로 울타리 내부의 늑대와 양의 개수를 세고, return 값으로 늑대와 양을 반환했다. 어떤 칸에 대해 방문하지 않았다고 하면 무조건 bfs로 탐색하였다. from collections import deque import queue from re import T def bfs(a, b): queue = deque([(a, b)]) wolf = 0 sheep = 0 while queue: x, y = queue.popleft() if arr[x][y] == "v": wolf += 1 elif arr[x][y] == "o": sheep += 1 for i in range(4): nx = x + dx[i] ny = y + dy[i] if n..