빵똥

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)에 도착했을 때 ..

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