Programming/Algorithm
-
[Java] 백준 2178 미로 탐색Programming/Algorithm 2021. 2. 25. 20:13
문제 (1,1)에서 (N,M)으로 이동하는 최단경로를 구하는 문제이다. 풀이 BFS로 map을 탐색하며 이동거리로 map을 초기화 했다. map[n][m]이 1이 아니게 되면 가장 먼저 도착지점에 다다른 것이므로 break하고 이동거리를 출력하도록 했다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int N, M; static int[][] map; static int AVAILAB..
-
[Java] 백준 2146 다리만들기Programming/Algorithm 2021. 2. 25. 20:08
문제 설명 섬과 바다가 있는 지도가 주어진다. 섬과 또 다른 섬을 잇는 다리를 만든다고 할 때, 가장 짧은 다리의 길이를 출력하라. 풀이 각 섬을 그룹화하여 번호를 붙이는 것은 어렵지 않았지만, 최단경로를 구하는 부분에서 어려움이 있었다. 최단경로를 구하는 메서드의 로직을 처음 푼 방식과 추후 수정한 방식 2가지로 정리해보았다. 1. (처음 푼 방식) 섬 1개를 기준으로 탐색하여 다른 섬을 발견하면 탐색을 멈추는 방식 - 최단경로를 구하기 위해서 이동거리를 담을 배열 visited를 Integer.MAX_VALUE로 초기화한다. int[][] visited = new int[N][N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { visite..
-
[Java] 백준 7576 토마토Programming/Algorithm 2021. 2. 23. 04:23
문제 M x N 크기의 상자와 각 칸에 들어있는 토마토의 상태가 주어진다. (1: 익은 토마토, 0: 안익은 토마토, -1: 토마토 없음) 익은 토마토는 인접한 안익은 토마토를 익게만든다고 할 때, 토마토가 모두 익을 때까지 최소 날짜를 출력해라. 모두 익을 수 없는 경우엔 -1, 이미 모두 익어있는 경우엔 0을 출력한다. (2 = N || y = M) return false; return true; } static class Point { int x, y, days; public Point(int x, int y, int days) { this.x = x; this.y = y; this.days = days; } } } 채점결과
-
[Java] 백준 4963 섬의 개수Programming/Algorithm 2021. 2. 23. 04:10
문제 섬(1)과 바다(0)로 이루어진 지도가 주어진다. 이어져 있는 섬은 하나의 섬으로 간주할 때, 섬의 총 개수를 출력해라. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class b4963 { static int W, H; static int[][] map; static int SEA = 0, LAND = 1, VISITED = 2; public static void main(String[] args) thro..
-
[Java] 백준 9466 텀 프로젝트Programming/Algorithm 2021. 2. 22. 10:14
문제 학생의 수 N과 1부터 N까지의 학생이 팀을 이루고 싶은 학생 번호가 주어진다. 어떤 팀에도 속하지 않는 학생의 수를 계산해라. - 학생 수 (2 0) total -= cnt; }// for sb.append(total).append("\n"); } System.out.println(sb); } } 2. DFS 풀이 - 각 학생이 선택한 학생번호를 담을 int배열 students, 방문 확인여부를 담을 boolean배열 visited, 덧셈 확인여부를 담을 boolean배열 checked를 둔다. - for문을 돌며 각 학생들이 팀을 이룰 수 있는지 확인한다. - dfs(학생번호)를 재귀적으로 호출한다. - 현재 학생이 아직 방문하지 않은 상태라면 visited[학생번호]를 true로 변경하고 다음..