0과 1의 쉼터

문제https://www.acmicpc.net/problem/18405 풀이N * N크기의 보드에서 번호가 낮은 바이러스부터 상하좌우로 증식한다.이 때, S초 후 ( X, Y )에 위치한 바이러스를 출력하는 문제다.우선 ( X, Y )에 시작부터 바이러스가 있을 수 있다. 확인 후 탐색을 진행하자. private static int bfs() { if (A[X - 1][Y - 1] != 0) return;번호가 낮은 바이러스 먼저 증식해야 하기 때문에 바이러스를 찾아, 바이러스 번호에 대해 오름차순으로 정렬 후 큐에 담아주자. List list = new ArrayList(); for (int i = 0; i 0) { ..

문제https://school.programmers.co.kr/learn/courses/30/lessons/43162?language=python3 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  풀이그래프의 간선이 2차원 배열로 주어졌을 때, 독립된 정점 그룹의 수를 세는 문제다.정점의 수는 최대 200이므로 완전 탐색을 하기에 시간이 충분하다.BFS를 하며 연결된 정점들을 전부 탐색 후 그룹의 수를 증가시키는 방식으로 해결했다.def solution(n, computers): visited = [False] * n cnt = 0 for i in range(n): if n..

문제https://www.acmicpc.net/problem/1405 풀이로봇이 확률에 따라 상하좌우로 움직인다고 한다.이동 가능한 모든 경로에 대해, 방문하지 않은 곳을 방문하는 비율을 구하는 문제로 재해석할 수 있다.주어진 상하좌우로 움직이는 확률을 방향 좌표와 함께 묶어주자.문제에서 주어진 N은 14이기 때문에 -14 ~ 14를 고려해 보드의 크기는 29면 충분하다.if __name__ == '__main__': visited = [[False] * 29 for _ in range(29)] # Input N, *D = map(int, input().split()) D = [(*point, d * 0.01) for point, d in zip([(0, 1), (0, -1)..

문제https://www.acmicpc.net/problem/2178 풀이주어진 보드의 (0, 0)에서 (N - 1, M - 1)에 도달하기 위해 움직인 최소 횟수를 구하는 문제다.BFS로 탐색을 진행했다.if __name__ == '__main__': # Input N, M = map(int, input().split()) board = [[*map(int, input().rstrip())] for _ in range(N)] # Solve & Output print(bfs(N - 1, M - 1))큐에는 현재 위치 (x, y)를 담았으며, 따로 방문 횟수를 기록해도 되지만 주어진 board를 활용했다.빈 공간은 1로, 이동하면서 기존 위치의 값 + 1으로 채웠다.이미 방문한 ..

문제https://www.acmicpc.net/problem/1697 풀이0 이상 10만 이하의 N과 K에 대해 다음 연산을 통해 N이 K가 되는 가장 빠른 연산 횟수를 구하는 문제다.BFS를 통해 (연산 결과, 연산 횟수) 쌍을 큐에 담아줬다.from collections import dequefrom sys import stdininput = stdin.readlinedef bfs(start, end): queue = deque([(start, 0)]) visited = [False] * 100_001 visited[start] = True요소를 하나씩 제거하며 연산 결과가 K가 될 때 까지 반복했으며,새로운 N은 0 ~ 100,000을 벗어나지 않고, 계산해본 적 없는 수에 대해서만..

문제https://www.acmicpc.net/problem/3055 풀이S에 위치한 고슴도치가 비버의 굴 D로 이동하는데 필요한 최소 시간을 구하는 문제다.동시에, 물 또한 인접한 영역으로 퍼져나간다.물이 찰 예정인 영역은 고슴도치가 갈 수 없다. → 고슴도치보다 물 먼저 퍼져야 한다.물은 비버의 굴로 퍼질 수 없다.우선, 상수들을 정의해주자. final static char EMPTY = '.', WATER = '*', START = 'S', END = 'D'; static int[][] D = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} }; static int R, C; static char[][] board; ..

문제https://www.acmicpc.net/problem/6118  풀이양방향 그래프의 1번 정점으로부터의 최대 깊이를 가지는 정점의 번호와 깊이, 동일한 최대 깊이를 가지는 정점의 수를 구하는 문제다.양방향 그래프부터 구성하자.import java.io.*;import java.util.*;public class Main { static List> graph = new ArrayList(); static int N; static int[] depth; public static void main(String[] args) throws IOException { // Init BufferedReader br = new BufferedReader(new Inp..

문제https://www.acmicpc.net/problem/1325  풀이단방향 그래프가 주어질 때, 가장 많은 정점을 방문할 수 있는 시작 정점을 찾는 문제다.A가 B를 신뢰할 때 B가 해킹 당하면 A도 해킹 당한다. 신뢰 관계에 대한 단방향 그래프를 구성하자.import java.io.*;import java.util.*;public class Main { static List> graph = new ArrayList(); static int N; static int[] cnt public static void main(String[] args) throws IOException { // Init BufferedReader br = new Buffere..

문제https://school.programmers.co.kr/learn/courses/30/lessons/42898풀이MN크기의 보드에 장애물이 주어지고, (1, 1)에서 (M, N)까지 가는 최단 경로의 수를 1e9 + 7로 나눈 나머지를 출력하는 문제다.보통 좌표가 NM으로 주어지지만 여기서는 MN이다. puddles가 가지는 좌표또한 MN임을 유의하자.puddles에는 BLOCK표시를 해주자.( 0, 1 ) 또는 ( 1, 0 )에 1을 기입해 (1, 1)이 1을 가질 수 있도록 해주자.dp[i][j] : ( i, j )까지 오는 최단 경로의 수이후에는 모든 경로를 탐색하며 장애물이 없는 칸이라면 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]을 통해 최단 경로의 수를 합쳐주자..

문제https://www.acmicpc.net/problem/11438풀이기존에 선형 탐색으로 O(N)만에 LCA를 구하는 방법으로는 이 문제를 해결할 수 없다.2025.01.15 - [PS/Baekjoon Online Judge] - [백준 11437] LCA [Java] [백준 11437] LCA [Java]문제https://www.acmicpc.net/problem/11437풀이DFS를 통해 모든 노드의 부모 노드와, 깊이를 구한 후 LCA를 구하는 기본 문제입니다.이를 위해서 양방향 그래프를 구성해야 합니다.문제에서 트리의 루트는 1kyr-db.tistory.com각 쿼리에 대해 O(logN)안에 LCA를 찾을 수 있는 방법에 대해 알아보자.깊이가 다른 두 노드의 깊이를 맞추고 LCA를 탐색하는 ..