[이것이 코딩테스트다] 24일차 - 최단경로 알고리즘 예제풀이 | 플로이드, 정확한 순위, 화성탐사, 숨바꼭질

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

Chapter 9 최단경로 알고리즘

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

[백준 11404] 플로이드

문제

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

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

 

입력 조건

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

접근 방법

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

입력 조건 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)