hwooo

https://www.acmicpc.net/problem/3109풀이dfs로 탐색하되, 최대한 많은 파이프를 연결할 수 있게 위-중간-아래의 방향으로 탐색해야 한다.또한 방문처리 후 실패한 경로라도 되돌려놓지 않는다.[1,1]- > [2,2] -> [2,3] 일 때 실패한다면 [2,2]에서 가는 모든 길이 실패하기에 방문한 곳은 다시 한 번 방문하지 않는다. Java 코드import java.io.BufferedReader;import java.io.InputStreamReader;public class Main { static int N, M; static char[][] map; static boolean[][] visited; public static void main(Stri..

https://www.acmicpc.net/problem/1194풀이BFS로 탐색하되, visited 배열을 3차원을 만든다.칸을 방문할 때 어떤 키를 가지고 방문했는지 확인해서, 같은 상태일 때 방문하는 걸 막는다.key를 비트값으로 저장하여 문을 만났을 때 key가 있는지 확인한 후 있다면 방문이 가능하게 탐색한다.Java 코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.List;import java.util.Queue;public class Main { static int N, M; static..

https://www.acmicpc.net/problem/17472풀이먼저 bfs로 섬을 나눈다. 나눈 후 섬인 곳에서 다른 섬까지의 길이를 찾는다. 이 때 길이 꺾이면 안 되므로 4방향으로 이동한 후, 다른 섬이 있다면 [출발, 도착, 길이]를 저장한다.모든 섬과 섬 사이의 거리를 구했다면, 이를 길이가 짧은 순으로 정렬하고, 짧은 것부터 이어주며 union-find를 진행한다.다 이어준 후에 find()를 한 번 더 실행하여 연결된 그룹들의 루트를 통일해준 후 하나라도 루트가 다른 게 있다면 -1을, 아니라면 구한 값을 출력한다.Java 코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayDeque..

https://www.acmicpc.net/problem/2146풀이bfs로 섬을 찾은 후, 다시 bfs로 섬 위의 어떤 점에서 다른 섬으로 가는 최단 거리를 찾는다.섬의 최대 크기가 100 * 100이므로 브루트포스로 탐색한다.Java 코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.Queue;public class Main { static int N, groupNum = 2; static int[][] map; static boolean[][] visited; public static void main(String args[]) th..

https://www.acmicpc.net/problem/17490풀이노드끼리의 연결 정보를 저장한 후, 이를 바탕으로 각 그룹으로 묶어준다.이 때 모두 하나의 그룹에 묶인다면 와우도를 사용하지 않아도 되므로 YES 출력 후 프로그램을 종료한다.1개 이상이라면 와우도까지의 돌의 개수를 오름차순으로 정렬, 가장 돌이 적게 드는 곳부터 연결한다.이 때 해당 그룹에서 다리가 이미 연결되었다면 다른 다리가 추가로 필요하지 않으므로 set에 그룹의 정보를 저장한 후, 한 그룹에서 하나의 다리만 연결되게 한다.연결 도중 돌의 개수가 K개가 넘었다면 NO를 출력하고, 아니라면 YES를 출력한다.Java 코드import java.io.BufferedReader;import java.io.InputStreamReader..

https://www.acmicpc.net/problem/14890풀이같은 높이인 칸의 연속된 개수를 세어서 사용한다.올라가는 경우에는 현재까지 세어 둔 수를 활용하고, 내려가는 경우에는 낮은 칸의 갯수를 센다.각 칸의 개수가 L개보다 작다면 false를 반환한다. 이 때 내려갔다가 올라가는 경우에는 경사로가 겹치면 안 되기에 L의 2배 길이가 필요하다.L = 2일 때, 3 3 2 2 3 3 (X), 3 3 2 2 2 2 3 3 (O)따라서 내려가는 경우에는 세어둔 칸의 개수에서 L만큼을 빼서 다음 계산에 사용한다.Java 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import jav..

https://www.acmicpc.net/problem/1600풀이원숭이가 K번까지는 말처럼 뛸 수 있다. 따라서 K번 뛰기 전까지는 같은 구역에 몇 번이고 방문할 수 있다. 따라서 bfs에서 방문 체크를 할 때 K 번까지 가능하게 해야 하므로 각 좌표마다 K번 체크할 수 있게 visited 배열을 3차원으로 만들어야 한다. 이 때 K번을 다 뛰었음에도 계속 갈 수 있으므로 visited 배열의 크기는 [H][W][K + 1]개로 선언되어야 한다.이 외에는 bfs 알고리즘과 동일하며, 시작 지점과 출발 지점이 같을 때의 예외 처리가 필요하다.Java 코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arra..

https://www.acmicpc.net/problem/17471풀이풀이 의도 작성N의 최대 값이 10이므로 완전탐색으로 선거구를 나눈다. 도시 간의 연결과 상관 없이 구역을 나눈 후, 각 구역 내의 도시들이 모두 연결되어 있는지 확인한다.연결되어 있다면 해당 구역들 간의 인구 수의 차이를 구한 후, 최소인 값을 갱신한다. 이 때 group 이라는 boolean 배열로 나누었는데, 선택받은 그룹으로 하나, 선택받지 않은 그룹으로 하나 총 2개로 나뉘어야 한다. 문제에서는 그룹을 총 2개로 나누기에 선택받지 않은 그룹끼리도 묶여 있는지를 확인해야한다. Java 코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util..