JUINTINATION

문제 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 풀이 그래프의 정점의 집합을 둘로 분할했을 때 각 집합에 속한 정점끼리 서로 인접하지 않도록 분할할 수 있는 그래프인 이분 그래프(Bipartite Graph)를 판별하는 문제입니다. 접근 처음에 문제를 다음 그림과 같이 잘못 이해했습니다. 그래서 유니온 파인드 알고리즘으로 접근하고자 했지만 예제에서부터 답이 다르게 출력됐습니다. 이분 그래프는 다음과 같습니다. 번호가 1부터 6까지 있는 정..

문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 n×m의 행렬로 표현되는 맵에서 0은 이동할 수 있는 곳을, 1은 벽을 나타냅니다. 상하좌우로 인접한 칸으로 이동할 수 있고 벽을 1개 부술 수 있을 때 (1, 1)에서 (n, m)까지의 최단 거리를 구하는 문제입니다. 접근 그래프의 간선에 가중치가 없기 때문에 다익스트라 대신 bfs로 문제 해결이 가능합니다. 어떤 좌표에 방문 여부를 확인할 수 있는 visit..

문제 https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 풀이 각 면에 1부터 6까지 수가 하나씩 적혀있는 정육면체 주사위를 사용하며 총 100개의 칸으로 나누어져 있는 보드판이 있을 때 플레이어는 주사위를 굴려 나온 수만큼 이동해야 합니다. 이때 주사위를 굴린 결과가 100번 칸을 넘어간다면 이동할 수 없으며 사다리가 있는 칸에 도착하면 사다리를 따라 위로 올라가고 뱀이 있는 칸에 도착하면 뱀을 따라..

문제 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 익은 토마토는 앞, 뒤, 왼쪽, 오른쪽, 위, 아래 여섯 방향에 인접해있는 익지 않은 토마토를 하루가 지나면 익게 만들 수 있을 때 모두 익을 때까지 최소 날짜를 구하는 문제입니다. 지난번에 풀었던 다른 토마토 문제의 풀이와 유사합니다. 코드 자바 import java.io.IOException; import java.io.BufferedReader; import..

문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 익은 토마토는 앞, 뒤, 왼쪽, 오른쪽 네 방향에 인접해있는 익지 않은 토마토를 하루가 지나면 익게 만들 수 있을 때 모두 익을 때까지 최소 날짜를 구하는 문제입니다. 코드 자바 import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.uti..

문제 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 0번부터 N-1번으로 번호가 매겨진 사람들 중에 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 확인하는 문제입니다. A는 B와 친구다. B는 C와 친구다. C는 D와 친구다. D는 E와 친구다. 코드 자바 import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTok..