오딩이

문제 출처 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 2개의 연속된 칸을 차지하는 파이프를 3가지 방향으로 밀면서 회전시켜서 파이프의 한쪽 끝을 (N,N)으로 이동시키는 방법의 개수를 구하는 문제였습니다. 처음에는 dr, dc의 방향 배열과 위치와 가로, 세로, 대각선 중 어떤 상태인지를 가지는 클래스를 생성하여 bfs로 풀려고 했지만, 따져야 할 조건들이 많아 결국 dfs 재귀 형식으로 풀었습니다. 파이프는..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이 유니온 파인드를 사용하여 해결하였습니다. 경로의 최단경로나 최소개수를 구하는 문제가 아니기때문에 크루스칼 알고리즘까지 할 필요가 없었고, 다른 과정 없이 union-find 로직을 통해 같은 경로에 있는지만 확인 후 true, false를 체크하였습니다. 루트노드가 같은 루트노드라면 같은 경로에 있다고 판단할 수 있습니다. 전체 코드 import java.io.BufferedReader; i..

https://www.acmicpc.net/problem/16202 16202번: MST 게임 첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있 www.acmicpc.net 풀이 크루스칼을 이용해서 해결했습니다. 기존 MST문제들은 무조건 MST를 만들어야해서 편하게 크루스칼을 사용하면 되지만, 이 문제는 MST가 만들어지지 않을 수도 있어서 MST인지 판단해야 하는 로직이 어려웠습니다. 간선을 하나씩 지울 때 마다 노드가 지워지는지 확인하고, 노드가 지워지면 root노드를 초기화해야 합니다. 간선을 지..

https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 풀이 크루스칼 알고리즘을 사용했습니다. 이미 연결되어있는 노드들을 먼저 연결한 뒤, 우주신들의 좌표대로 크루스칼 알고리즘을 사용하여 MST를 구현했습니다. 크루스칼 알고리즘을 사용하는 것은 어렵지 않았지만, 좌표를 처리할 Pos클래스를 따로 만들어 처리해야 해서 처음 구상이 어려웠습니다. 전체 코드 import java.io.BufferedReader; import ja..