JUINTINATION

문제 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 풀이 여러 섬으로 이루어진 나라에서 한 섬과 다른 섬을 잇는 다리 하나를 만든다고 할 때 가장 짧은 다리의 길이를 구하는 문제입니다. 이때 섬은 동서남북으로 붙어있는 땅을 의미합니다. 접근 어떤 섬과 다른 섬 사이를 잇는 다리를 만들어야 하므로 각 섬이 다른 섬이라는 것을 표시해야 합니다. 여러 가지 알고리즘을 사용할 수 있지만 저는 dfs 알고리즘을 이용하여 각 섬에 번호를 정해주었습니다. 입력..

문제 https://www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net 풀이 정점에 1부터 n까지 번호가 매겨져 있는 양방향 그래프를 표현한 트리가 있을 때 어떤 수열이 BFS 알고리즘을 이용했을 때 해당 수열의 순서대로 방문할 수 있는지 확인하는 문제입니다. 이때 정점을 방문하는 순서는 중요하지 않습니다. 접근 BFS, DFS 알고리즘은 정점끼리 어떤 순서로 연결돼있는지에 따라 방문 순서가 달라집니다. 하지만 이 문제에서는 방문 방문가 먼저 나온 뒤에 이 순서대로 출력이 가능한지 확인해야 합니다. 그래서 저는 정점에 연결된 다른 정점들을 ArrayList 배열인 list로 표..

문제 https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 풀이 한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선을 순환선이라고 하고 두 역(정점) 사이의 거리는 지나야 하는 구간(간선)의 개수일 때 1개의 순환선과 각 역과 순환선 사이의 거리를 구하는 문제입니다. 접근 dfs를 이용하여 방문한 적이 있는 역으로 다시 돌아왔다면 해당 역을 기준으로 순환선이 만들어지고 그 안에 있는 모든 역에 순환선이라..

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