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/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://www.acmicpc.net/problem/6593풀이L, R, C로 이루어진 직육면체에서 상하좌우, 위, 아래로만 이동하며 출발지 S에서 도착지 E로 도착하는데 걸리는 최단 시간을 구하는 문제다.BFS를 3차원으로 확장하면 되는 기본 문제다.우선 시작 전 문자나 상태를 정의해주자.상위 그래프 문제로 갈수록 이처럼 문제에서 주어지는 문자들을 자신의 언어로 변환해주는게 실수를 방지하는데 도움이 된다.L, R, C가 모두 0이 아닐 때 까지 입력을 받으며 탐색을 진행하면 된다.그래프 정보를 입력받으며 벽을 표시해주고, 시작점과 종료점의 위치를 파악해주자.(sl, sr, sc, el, er, ec)각 층마다 한 줄 공백 입력이 주어진다는 점에 유의하자.기본 BFS를 3차원으로 확장해 구현해주..

문제https://www.acmicpc.net/problem/2583풀이K개의 직사각형을 제외한 나머지 영역의 개수와 넓이를 구하는 문제다.우선 문제의 예제를 살펴보자.K개의 직사각형에 대해 표시하면 다음과 같다. 왼쪽아래 좌표와 오른쪽위 좌표가 주어지는데 그림을 회전시켜보자.일반적인 배열의 논리적 표현과 같다.그러면 사각형의 넓이는 어떻게 구할까?전체적으로 행과 열을 축소시키면 된다.즉, 이 문제에서 다룰 범위는 M, N에 대해 (0, 0) ~ (N - 1, M - 1)가 된다.K개의 좌표를 입력받아 블럭표시를 해주자.이제 블럭( BLCOK )이 아니고, 방문한적 없는( EMPTY )영역들에 대해 BFS를 진행하면된다.bfs(i, j)는(i, j)에서 bfs를 하고, 하나로 연결된 영역의 넓이를 반환한..

문제https://www.acmicpc.net/problem/17071풀이수빈이와 동생이 각각 N, K에서 이동할 때 몇 초 후에 서로 만날 수 있는지 계산하는 문제다.수빈이는 다음과 같이 움직일 수 있다.X - 1X + 12X동생은 다음과 같이 움직일 수 있다.N + KK는 경과 시간이자. 동생이 움직일 수 있는 거리를 의미한다. 풀이에서는 step으로 표현하겠다.만약 N == K인 경우 수빈이와 동생은 제자리에서 만나므로 탐색이 불필요하다. 걸린 시간은 0초다.bfs로 N부터 탐색을 시작하자.큐가 비어있거나, k(동생의 이동 위치)가 500,000이하라면 탐색을 계속해야 하므로 동생의 이동거리부터 계산하며 조건식에 포함시켜주자.본격적으로 풀이를 하기전에 시간복잡도에 대해 생각해보자.수빈이는 X - 1..