[이것이 코딩테스트다] 24일차 - 최단경로 알고리즘 예제풀이...

[이것이 코딩테스트다] 24일차 - 최단경로 알고리즘 예제풀이...

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다.

Chapter 9 최단경로 알고리즘

오늘 풀이한 문제 - 최단경로 알고리즘 예제

문제

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력 조건

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다. 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

접근 방법

문제이름처럼 플로이드 워셜 알고리즘으로 풀이할 수 있는 문제이다

입력 조건 5번에 따르면 도시를 잇는 경로가 2개 이상일수 있으므로 cost table에서 c를 받을때 기존값과 비교하여 가장 작은값만 저장하도록 한다

소스 코드

## 플로이드 워셜 n = int(input()) m = int(input()) INF = 1e9 graph = [[INF]*(n+1) for _ in range(n+1)] ## 자기자신에게 가는 비용 = 0 for i in range(1,n+1): for j in range(1, n+1): if i == j: graph[i][j]=0 for _ in range(m): a,b,c = map(int, input().split()) graph[a][b] = min(c, graph[a][b]) ## 경로가 2개 이상일경우 최소 경로만 저장 for k in range(1,n+1): for a in range(1, n+1): for b in range(1, n+1): graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]) for result in graph[1:]: for element in result[1:]: if element == INF: print (0, end = ' ') else: print (element, end = ' ') print()

[이코테 386p] 정확한 순위

문제

선생님은 시험을 본 학생 N명의 성적을 분실하고, 성적을 비교한 결과의 일부만 가지고 있다. 학생 N명의 성적은 모두 다른데, 다음은 6명의 학생에 대하여 6번만 성적을 비교한 결과이다.

1번 학생의 성적 < 5번 학생의 성적

3번 학생의 성적 < 4번 학생의 성적

4번 학생의 성적 < 2번 학생의 성적

4번 학생의 성적 < 6번 학생의 성적

5번 학생의 성적 < 2번 학생의 성적

5번 학생의 성적 < 4번 학생의 성적

A번 학생의 성적이 B번 학생보다 낮다면 화살표가 A에서 B를 가리키도록 한다.

학생들의 성적을 비교한 결과가 주어질 때, 성적 순위를 정확히 알 수 있는 학생은 모두 몇명인지 계산하는 프로그램을 작성하라.

입력 조건

첫째 줄에 학생들의 수 N (2 <= N <= 500)과 두 학생의 성적을 비교한 횟수 M(2 <= M <= 10,000)이 주어진다.

다음 M개의 각 줄에는 두 학생의 성적을 비교한 결과를 나타내는 두 양의 정수 A와 B가 주어진다. 이는 A번 학생의 성적이 B번 학생보다 낮다는 것을 의미한다.

접근 방법

플로이트워셜로 풀어야한다는건 알았는데 어떻게 판단해야 성적순위를 정확히 알수있는 학생으로 판별하는지 기준을 세우기 어려웠다

살짝 힌트를 얻고^^ (from google)

학생 리스트로 이차원 배열을 만들었을때

행의 의미 : 나보다 성적이 높은 친구들

열의 의미 : 나보다 성적이 낮은 친구들

따라서 플로이드 워셜 알고리즘을 통해 각 학생을 연결하는 최소 거리를 구했을때

정확히 성적 순위를 알 수 있는 학생은 x,y 좌표가 들어왔을때 x,y 나 y,x 좌표가 하나라도 채워져 있는 학생이다

아래 표에서 4번학생은 순위가 정해진 학생임

1 2 3 4 5 1 0 1 2 0 2 3 0 inf 4 inf inf 2 0 4 5 inf 0

소스 코드

n, m = map(int, input().split()) ## 노드, 간선 개수 INF = 1e9 graph = [[INF]*(n+1) for _ in range(n+1)] for i in range(n+1): for j in range(n+1): if i == j: graph[i][j] = 0 for _ in range(m): a,b = map(int, input().split()) graph[a][b] = 1 for k in range(1, n+1): for a in range(1,n+1): for b in range(1,n+1): graph[a][b] = min(graph[a][b] , graph[a][k]+graph[k][b]) result = 0 for i in range(1,n+1): count = 0 for j in range(1, n+1): if graph[i][j] != INF or graph[j][i] != INF: count += 1 if count == n: result += 1 print (result)

[이코테 388p] 화성 탐사

문제

당신은 화성 탐사 기계를 개발하는 프로그래머다. 그런데 화성은 에너지 공급원을 찾기가 힘들다. 그래서 에너지를 효율적으로 사용하고자 화성 탐사 기계가 출발 지점에서 목표 지점까지 이동할 때 항상 최적의 경로를 찾도록 개발해야 한다. 화성 탐사 기계가 존재하는 공간은 N x N 크기의 2차원 공간이며, 각각의 칸을 지나기 위한 비용(에너지 소모량)이 존재한다. 가장 왼쪽 위 칸인 [0][0] 위치에서 가장 오른쪽 아래 칸인 [N - 1][N - 1] 위치로 이동하는 최소 비용을 출력하는 프로그램을 작성하라. 화성 탐사 기계는 특정한 위치에서 상하좌우 인접한 곳으로 1칸씩 이동할 수 있다.

입력 조건

첫째 줄에 테스트 케이스의 수 T(1 <= T <= 10)가 주어진다.

매 테스트 케이스의 첫째 줄에는 탐사 공간의 크기를 의미하는 정수 N이 주어진다. 2 <= N <= 125

이어서 N개의 줄에 걸쳐 각 칸의 비용이 주어지며 공백으로 구분한다. 0 <= 각 칸의 비용 <= 9 .

접근 방법

다익스트라 알고리즘을 이용하여 풀었다

2차원 graph 리스트를 만들어 각 위치의 cost를 저장하고 이를 풀이에 활용

아직은 조금 어색한지 기본코드를 약간씩 참고해서 풀음^^,,

코테에서 봤으면 bfs/dfs를 이용해 풀으려 했을것 같기도 하다,,,,

소스 코드

import heapq n = int(input()) INF = 1e9 graph = [] distance = [[INF]*(n) for _ in range(n)] for i in range(n): graph.append(list(map(int, input().split()))) q =[] heapq.heappush(q, (graph[0][0],0,0)) dx = [-1, 1, 0, 0] dy = [0, 0, 1, -1] while q: dist, x, y = heapq.heappop(q) if distance[x][y] < dist : continue for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0 <= nx < n and 0 <= ny < n: cost = dist + graph[nx][ny] if cost < distance[nx][ny]: distance[nx][ny] = cost heapq.heappush(q,(cost, nx, ny)) print (distance[-1][-1])

[이코테 390p] 숨바꼭질

문제

동빈이는 숨바꼭질을 하면서 술래로부터 잡히지 않도록 숨을 곳을 찾고 있다. 동빈이는 1 ~ N번까지의 헛간 중에서 하나를 골라 숨을 수 있으며, 술래는 항상 1번 헛간에서 출발한다. 전체 맵에는 총 M개의 양방향 통로가 존재하며, 하나의 통로는 서로 다른 두 헛간을 연결한다. 또한 전체 맵은 항상 어떤 헛간에서 다른 어떤 헛간으로 도달이 가능한 형태로 주어진다.

동빈이는 1번 헛간으로부터 최단 거리가 가장 먼 헛간이 가장 안전하다고 판단하고 있다. 이 때 최단 거리의 의미는 지나야 하는 길의 최소 개수를 의미한다. 동빈이가 숨을 헛간의 번호를 출력하는 프로그램을 작성해라.

입력 조건

첫째 줄에는 N과 M이 주어지며, 공백으로 구분한다.(2 <= N <= 20,000), (1 <= M <= 50,000)

이후 M개의 줄에 걸쳐서 서로 연결된 두 헛간 A와 B의 번호가 공백으로 구분되어 주어진다.(1 <= A, B <= N)

접근 방법

다익스트라 알고리즘을 사용

양방향으로 연결되기 때문에 graph 한번에 1로 값 지정

소스 코드

import heapq n, m= map(int, input().split()) INF = 1e9 graph = [[] for i in range(n+1)] distance = [INF]*(n+1) for i in range(m): a,b = map(int, input().split()) graph[a].append((b,1)) graph[b].append((a,1)) q = [] heapq.heappush(q, (0, 1)) distance[1] = 0 while q: dist, now = heapq.heappop(q) if dist > distance[now]: continue for info in graph[now]: cost = dist + info[1] if cost < distance[info[0]]: distance[info[0]] = cost heapq.heappush(q, (cost, info[0])) ## 숨어야 하는 헛간의 번호 , 숨어야하는 헛간까지의 거리, 숨어야하는 헛간과 같은 거리를 가지는 헛간의 개수 출력 target_num = 0 target_dist = 0 same_dist = 0 for idx,d in enumerate (distance): if d != INF: if d > target_dist: target_dist = d target_num = idx same_dist = 0 if target_dist == d : same_dist += 1 print (target_num, target_dist, same_dist)

from http://gammistory.tistory.com/44 by ccl(A) rewrite - 2021-12-30 00:26:25