JUINTINATION

문제 https://www.acmicpc.net/problem/16964 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루 www.acmicpc.net 풀이 지난 BFS 스페셜 저지 문제에 이어 정점에 1부터 n까지 번호가 매겨져 있는 양방향 그래프를 표현한 트리가 있을 때 어떤 수열이 DFS 알고리즘을 이용했을 때 해당 수열의 순서대로 방문할 수 있는지 확인하는 문제입니다. 이때 정점을 방문하는 순서는 중요하지 않습니다. 접근 BFS, 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/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 풀이 Two Dots는 Playdots, Inc. 에서 만든 게임으로 같은 색으로 이루어진 사이클을 찾는 게임입니다. 이 게임에서 대각선으로는 움직일 수 없을 때 최소 4개의 점을 잇는 사이클이 존재하는지 여부를 확인하는 문제입니다. 접근 오른쪽으로 갔다가 바로 왼쪽으로 오면 2개의 점으로 사이클이 만들어지기 때문에 문제 조건에 부합합니다. 따라서 처음에는 dfs 함수 내부의 매개변..

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