본문 바로가기

알고리즘55

백준_11404_플로이드 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다. 시작 www.acmicpc.net 해결 방법 >문제가 모든 도시에서 갈 수 있는 도시까지의 최소거리를 구하는 문제이다. >문제의 제목에서 알 수 있듯이 플로이드 알고리.. 2020. 1. 21.
백준_4963_섬의 개수 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러쌓여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 www.acmicpc.net 해결 방법 > DFS를 이용한다. 고찰 > 문제를 보자마자 입력을 어떻게 받아야 할지 고민하였다. 줄마다 입력 개수가 다르기 떄문이다. >.. 2020. 1. 20.
백준_1389_케빈 베이컨의 6단계 법칙 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다. www.acmicpc.net 해결 방법 > 각 사람들을 하나의 노드하고 생각하였다. > 케빈의 베이컨 수는 각 노드에서 나머지 노드까지의 최단 거리의 합이다. > 플로이드 워.. 2020. 1. 17.
백준_2178_미로 탐색 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 해결 방법 > BFS를 활용한다. > 미로에 최단거리의 업데이트를 하지 말고 또 다른 하나의 2차원 배열을 만들어 그곳에서 최단거리를 관리한다. > dx = [0,0,1,-1] dy = [1,-1,0,0]을 활용하여 상하좌우를 탐색한다. 코드 더보기 import collections y, x = map(int,input().split()) maze = [] queue = collections.deque([]) visited = .. 2020. 1. 16.

티스토리툴바