Algorithm

출처 https://www.acmicpc.net/problem/1976 접근 일반적인 DFS로 구현하면 각 여행경로를 확인하는데 O(N^3)1가 소요됩니다. 도시가 1000개이므로 200 x 200 x 200 x 1000 = 8,000,000,000(80억)으로 시간초과가 발생합니다. 해당 문제에서는 다른 도시를 몇번이든 방문할 수 있기 때문에, 일일히 경로를 방문하는 것은 시간초과를 유발합니다. 이를 최적화하기 위해 모든 여행계획이 같은 네트워크(루트를 공유)에 포함되는지 확인하기만 하면 됩니다. 이는 유니온 파인드(Union-find)로 구현할 수 있습니다. 풀이 package solving; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /* * [조건] * 시간 제한 : 2초, 메모리 제한 : 128MB * N <= 200, M <= 1000 * [구현] * 유니온 파인드를 통해 연결그래프를 구하고, 주어지는 여행계획이 같은 루트에 속하는지 확인한다. */ public class bj_1976_여행_가자 { static int N, M; static int[] root; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; N = Integer.parseInt(br.readLine()); M = Integer.parseInt(br.readLine()); root = new int[N + 1]; // 유니온 초기화 for (int i = 1; i <= N; i++) root[i] = i; for (int i = 1; i <= N; i++) { st = new StringTokenizer(br.readLine()); for (int j = 1; j <= N; j++) { // 두 도시를 같은 집합(루트)에 소속 if (st.nextToken().equals("1")) union(i, j); } } int[] plan = new int[M + 1]; st = new StringTokenizer(br.readLine()); for (int i = 1; i <= M; i++) plan[i] = Integer.parseInt(st.nextToken()); System.out.println(solve(plan)); } private static void union(int i, int j) { int ri = find(i); int rj = find(j); if (ri != rj) root[rj] = ri; } private static int find(int i) { if (i != root[i]) root[i] = find(root[i]); return root[i]; } private static String solve(int[] plan) { int r = find(plan[1]); for (int i = 2; i <= M; i++) { if (find(plan[i]) != r) return "NO"; } return "YES"; } } 결과 ...

출처 https://www.acmicpc.net/problem/14503 접근 N, M <= 50, O(N^5) = 312,500,000 이므로 시간복잡도는 여유롭게 구현 가능합니다. 로봇 청소기의 이동 방식을 BFS로 구현했습니다. 다시 생각해보니 BFS형태가 아니더라도 구현 가능한데 습관적으로 BFS를 사용한 것 같습니다. 문제에서 주어진 방향설정이 중요합니다. 북(-1, 0), 동(0, 1), 남(1, 0), 서(0, -1) 친절하게 방의 둘레는 모두 벽(1)로 채워져 있기 때문에 ArrayIndexOutOfBoundsException1은 처리하지 않아도 됩니다. 풀이 package solving; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; import java.util.StringTokenizer; /* * N, M이 50 이하이므로, 시간복잡도와 메모리제한은 고려하지 않음 * [풀이] * 로봇 청소기의 이동 방식을 bfs로 구현한다. * 방향 : 북(-1, 0), 동(0, 1), 남(1, 0), 서(0, -1) * 청소를 마치면 0 -> -1로 변경 * 로봇의 동작은 각각 별도의 메서드로 분리 */ public class bj_14503_로봇_청소기 { static int N; static int M; static int[][] room; static int[] dr = {-1, 0, 1, 0}; static int[] dc = {0, 1, 0, -1}; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); room = new int[N + 1][M + 1]; st = new StringTokenizer(br.readLine()); int[] start = {Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())}; int direction = Integer.parseInt(st.nextToken()); for (int i = 0; i < N; i++) { st = new StringTokenizer(br.readLine()); for (int j = 0; j < M; j++) room[i][j] = Integer.parseInt(st.nextToken()); } solve(start, direction); } private static void solve(int[] start, int direction) { Queue<int[]> q = new ArrayDeque<>(); q.offer(new int[]{start[0], start[1], direction}); int count = 0; while (!q.isEmpty()) { int[] cur = q.poll(); int r = cur[0], c = cur[1], d = cur[2]; // 현재 칸이 청소되지 않은 경우 if (room[r][c] == 0) { count++; room[r][c] = -1; } // 주변 4칸 중 빈칸이 없을 경우 if (!findDirty(r, c)) { int[] back = moveBack(r, c, d); if (back == null) break; q.offer(back); } // 주변 4칸 중 빈칸이 있을 경우 else { for (int i = 0; i < 4; i++) { d = d == 0 ? 3 : d == 3 ? 2 : d == 2 ? 1 : 0; int[] forward = moveForward(r, c, d); if (forward != null) { q.offer(forward); break; } } } } System.out.println(count); } private static int[] moveForward(int r, int c, int nd) { int nr = r + dr[nd]; int nc = c + dc[nd]; // 더이상 이동할 수 없을 때 if (room[nr][nc] != 0) return null; else return new int[]{nr, nc, nd}; } private static int[] moveBack(int r, int c, int d) { int nd = d == 0 ? 2 : d == 1 ? 3 : d == 2 ? 0 : 1; int nr = r + dr[nd]; int nc = c + dc[nd]; // 더이상 물러날 곳이 없을때 if (room[nr][nc] == 1) return null; else return new int[]{nr, nc, d}; } private static boolean findDirty(int r, int c) { for (int i = 0; i < 4; i++) { int nr = r + dr[i]; int nc = c + dc[i]; if (room[nr][nc] == 0) return true; } return false; } } 결과 ...

출처 https://www.acmicpc.net/problem/1806 접근 문제는 굉장히 심플하나, 시간제한이 0.5초이며 메모리 제한이 128MB인 것으로 보아 최적화 문제임을 알 수 있습니다. 주어지는 수열의 부분합을 구해야 하는데, 수열의 길이가 100,000이므로 O(N^2)으로는 시간 초과가 발생합니다. 부분합의 최대 크기를 100,000,000 ≒ 2^30 정도로 제한해주었기 때문에 int로 총합을 구해도 Overflow가 발생하지 않습니다. 풀이 포인터를 2개 두고 합이 S보다 커질때까지 부분수열의 크기를 늘리다가, S보다 커지는 시점부터 부분수열의 크기를 줄여나가면 됩니다. ①에서 점점 부분수열을 늘리다가 ②처럼 다시 15보다 작을때까지 사이즈를 줄여나갑니다. ...

출처 https://www.acmicpc.net/problem/4195 접근 처음에는 문제가 잘 이해되지 않았습니다.1 몇 번 읽어보니, 두 정점이 주어지면 두 정점을 연결하고 같은 그래프 내에 있는 모든 친구 개수를 출력하는 문제임을 알았습니다. ①, ②을 통해 연결된 네트워크는 각각 친구가 2명이며, ③을 통해 두 네트워크가 연결되면 총 친구는 4명입니다. 친구관계가 연결되어 같은 그래프에 포함되는 과정이 Union-Find 알고리즘과 동일하기 때문에, 이를 활용하여 해결할 수 있습니다. 유니온 파인드(Union Find) Union과 Find 메서드를 통해 서로소 집합2을 연결하는 알고리즘입니다. 각 집합의 단위는 Root로부터 하위 원소들로 구성되며, 모든 원소들은 동일한 Root를 바라보는 특징이 있습니다. Union과 Find를 간략히 그림으로 나타내면 다음과 같습니다. 노란색 : 부모 / 빨간색 : 유니온(Union) 메서드 / 파란색 : 파인드(find) 메서드 ...

출처 https://www.acmicpc.net/problem/12904 접근 처음에는 DP문제인줄 알고 접근했으나, 시간 초과로 실패했습니다.1 S로부터 T로 갈때는 여러 경로가 존재해서 DP와 같은 최적화가 필요해보입니다. S에서 시작할 경우 2^(T의 길이 - S의 길이) 만큼의 탐색이 필요합니다. 그러나 반대로 T에서 S로 갈때는 경로가 1개만 존재하므로, (T의 길이 - S의 길이)만큼만 탐색하면 S를 구할 수 있습니다. T에서 S로 갈때는 T의 맨뒤 값으로 이전 노드를 예측하는 것이 가능합니다. ...