빵똥

https://www.acmicpc.net/problem/18404 18404번: 현명한 나이트 첫째 줄에 N과 M이 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ N ≤ 500, 1 ≤ M ≤ 1,000) 둘째 줄에 나이트의 위치 (X, Y)를 의미하는 X와 Y가 공백을 기준으로 구분되어 자연수로 주어진다. ( www.acmicpc.net 1. 접근 나이트가 갈 수 있는 곳을 확인하는 게 500²에 M의 위치를 확인하여 출력하는 게 1000으로 BFS를 이용하여 시간 내에 충분히 풀 수 있는 문제이다. 먼저 나이트의 이동경로를 사용하기 편하게 배열로 저장하고 static int[][] dir = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1..

BFS 기초 문제 중 하나이다. 1. 접근 정점의 최대 갯수는개수는 100개이며 완전 그래프라 가정해도 간선의 개수는 n * (n - 1) / 2 = 100 * (100 - 1) / 2 = 4,950개, 그에 따른 무방향 그래프의 차수의 개수는 4,950 * 2 = 9,900개로 시간제한에 여유 있게 풀 수 있다. 2. 풀이 두 번째 입력값인 두 사람의 촌수, 즉 예제로 보자면 다음 그림과 같다. 다른 기초 BFS 문제와 같이 이동할 때 마다 배열에 1씩 누적하며 최종 목적지의 값을 출력하면 끝이다. 전역 변수 및 input static int V, E, start, end; static ArrayList[] graph; static int[] dist; public static void main(Str..

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 2178번과 같이 너비 탐색 기초 문제다. 1. 접근 테스트 케이스의 최대치가 나와있지는 않으나 체스판의 최대 크기인 300² 를 모두 밟아도 90,000으로 시간제한 걱정 없이 풀이에 접근하면 된다. 그림 예제에 나와있듯 나이트의 이동 경로를 미리 배열로 짜둔다면 다음과 같다. (시계방향) static int[][] dir = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, ..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 가중치 없는 그래프에서 최단 거리를 구하는 가장 기초적인 BFS 문제다. 1. 접근 미로의 모든 칸을 다 밟는다고 가정해도 최대 N * M, 즉 100²인 10,000으로 시간제한 1초 내에 풀 수 있다. 이동할 때의 조건으로는 다음과 같으며 배열로 미리 저장해두면 다음과 같으며 static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; 좌표상 (n - 1)(m - 1)에 도착했을 때 ..

DFS와 BFS를 동시에 활용해야 하는 문제인 백준 14502-연구소 문제를 풀어보자. (solved.ac 티어 = 골드 5) https://www.acmicpc.net/problem/14502 1. 접근 문제에서 확인할 수 있듯 그래프의 크기는 8 * 8 = 64가지이며 바이러스의 확산을 막는 벽을 반드시 3개를 설치해야 한다. 즉 우리가 해야 할 일은 벽을 3개 세워본다 -> 바이러스를 퍼트린다(0인 곳) -> 남아있는 안전지역을 확인한다 -> 최 갯값을 갱신한다. 이렇게 네 가지로 정리할 수 있으며 최댓값인 64개의 공간에 중복되지 않게 벽을 3개 세워본다 = n! / ((n - m)! * m!) = 41664 벽을 세운 후 하나하나 탐색하며 안전지대인지 확인한다 = N² = 64 시간 복잡도 = ..

10월 1일 퇴사 후 인프런 알고리즘 강의를 거쳐 백준에서 한 달 만에 겨우 골드 5단계 달성했다...! 다양한 유형을 접하고 있는 단계이며 취준 기간이 길어지더라도 조급해하지 하지 말고 천천히 가보려고 한다 백준, 인프런, 프로그래머스 등 한 문제씩 풀어갈 때마다 복습의 개념으로 블로그에 정리하고자 한다!