문제https://www.acmicpc.net/problem/1707풀이 이분 그래프를 판별하는 문제이다. 이분 그래프는 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프를 말한다. 풀이는 간단한데, 방문 시 1과 -1의 값으로 번갈아가며 방문 배열을 채워나가고, 만약 이전 방문 배열 값과 다음 방문 배열 값이 같으면 NO를 출력하면 끝이다. 그런데 여기서 주의해야할 것은 이분 그래프의 정의인데, 연결되지 않은 정점도 독립적인 그룹으로 이분 그래프의 조건을 만족한다. 그래서 탐색을 시작할 시작점은 방문되지 않은 점이 대상이 된다. (즉 모든 정점이 연결되어 있다고는 가정되어있지 않다! 이것땜에 43프로에서 틀렸다.) 다음은 소스 코드이다.소스 코드import..
자바
문제https://www.acmicpc.net/problem/11559 풀이bfs가 포함된 빡 구현 문제이다. 제거할 뿌요를 bfs로 찾고, 삭제하고, 중력을 통해 재 정렬을 해야한다. 여러 그룹의 삭제될 뿌요가 한 텀에 있어도 연쇄는 한 번이라는 것을 잊으면 안된다. 여기서 연속된 4개 이상이 연결된 뿌요를 찾아 제거해야하는데, 그냥 BFS를 사용해 탐색하면, ㅓ ㅏ ㅗ ㅜ 모양의 탐색은 visited에 걸려 탐색을 할 수가 없다. 이것은 단순하게 해결 가능한데, 최대 2번까지 방문을 허용하기만 하면 ㅓ ㅏ ㅗ ㅜ 탐색이 가능하게 된다. 중력에 의한 재정렬은 stack을 이용해 구현했다. 제거할 뿌요를 제외한 값을 stack에 push하고, 다시 map[][]의 아래부터 stack에서 pop을 하며 값..
문제https://www.acmicpc.net/problem/1461풀이정렬을 포함한 구현 문제이다. 처음에는 방문 배열을 적용해 탐색을 해야하나 싶었지만, 다시금 아이디어를 떠올려보니 단순 구현으로 해결될 것 같았다. "세준이가 한 번에 들 수 있는 책"을 보고, 가지고 있는 책의 매개변수를 관리해야하나 싶었는데, 여기서 책의 숫자는 배열상 인덱스 거리와 같기 때문에 단순 배열에서의 거리 이동으로 구현했다. 아이디어는 우선 center를 구한다. center는 세준이가 돌아오는 기점이면서 책을 충전하는 곳이다. 그러기 위해 배열을 입력받을 때 0 인덱스 위치를 포함시켰다. 배열을 정렬하고 값이 0인 인덱스 위치를 저장한다. 그리고 책을 놓으러 다닌다. 여기서 핵심 아이디어는 0에서 가장 멀리 떨어진..
문제https://www.acmicpc.net/problem/25192 풀이 엔터와 엔터 사이에 말하는 사람들은 반드시 한 번은 곰곰 이모티콘을 날린다. 이 말을 문제 요구사항에 맞게 해석하면, 엔터와 엔터 사이에 중복을 제외하고 카운트한 사람의 수를 구하라는 말이기도 하다. 이럴 때 가장 유용한 것은 Set 자료 구조이다. Set 자료구조에 값을 집어넣어 중복을 제거하고, Enter가 나오면 Set을 초기화한다. 아래는 소스 코드이다.소스 코드import java.util.HashSet;import java.util.Scanner;import java.util.Set;public class B25192_인사성밝은곰곰이 { public static void main(String[] args) {..
문제https://www.acmicpc.net/problem/14658 풀이N과 M의 범위가 500,000이고, 시간 제한은 2초기 때문에 주의해야한다. 별똥별 수인 K는 100개이기 때문에, K를 이용해 문제를 해결하면 시간 초과를 피할 수 있다. K를 이중 for문에서 순회하면서, 별똥별의 위치로 x, y 조합을 만든다.그림에서 노란 점이 별똥별이라면 만들 수 있는 조합은 회색 점과 같다. 즉 탐색을 시작할 후보군 정도로 생각할 수 있다. 회색 점에서 화살표 방향인 우 하단 방향으로 L만큼 측정하며, 범위에 해당하는 star를 카운트하고 가장 최대 값을 구하면 된다. 여기서, 후보군이 아니라 별똥별의 위치에서 탐색하면 되는 것 아닌가하는 의문이 들 수 있다.하지만, 만약 이렇게 다이아몬드 형태라..
문제https://www.acmicpc.net/problem/1774 풀이크루스칼을 이용해 MST를 구하는 문제입니다. 백준의 4386번. 별자리 만들기 문제와 상당히 비슷합니다. 이 문제의 핵심은 좌표(x, y)를 하나의 인덱스로 다루는 것이라고 생각합니다. 좌표를 입력받고, 좌표들을 간선으로 연결할 때에 인덱스를 매겨주며 ArrayList에 추가하고, 간선에 추가된 좌표의 위치는 거리를 구하기 위해서 필요할 뿐이지 더는 필요가 없으므로 시작과 종료 지점의 인덱스로 변환하고 좌표는 버립니다. 그리고 크루스칼 알고리즘을 인덱스로 실행하며 union시에 통로 길이 합을 더해주었습니다. 아래는 소스 코드입니다.소스 코드import java.util.ArrayList;import java.util.Col..
