백준 18352 - 파이썬

https://www.acmicpc.net/problem/18352

18352번: 특정 거리의 도시 찾기

문제 풀이

문제 풀이는 BFS를 기본적으로 사용하고, 도시와의 거리 단위는 1이기 때문에 방문시 현재 도시 기준에서 1을 더해준다. 

import sys
from collections import deque

input = sys.stdin.readline

n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n + 1)]

visited = [0] * (n + 1)

for _ in range(m):
  a, b = map(int, input().split())
  graph[a].append(b)
  # graph[b].append(a)


def bfs(x):
  q = deque()
  q.append(x)

  visited[x] = 1

  while q:
    x = q.popleft()
    for i in graph[x]:
      if not visited[i]:
        q.append(i)
        visited[i] = visited[x] + 1

# print(graph)
# print(visited)
bfs(x)
# visited.sort()

for i in range(n + 1):
  if not k + 1 in visited:
    print(-1)
    exit(0)
  elif k + 1 == visited[i]:
    print(i)

방문 리스트를 별도로 만들고, 방문시 1을 증가하도록 하였다. 출력은 방문 리스트에 k의 값이 없다면 -1을 출력 후 종료하고, 있다면 해당 인덱스를 출력하도록 했다.

 

문제를 맞춘 후 다른 사람들은 어떻게 풀었나 한번 찾아보았다. 첫번째 코드는 <이것이 코딩 테스트다>에 있는 코드이고, 두번째 코드는 이 분의 글을 참고했다. 마지막 세번째 코드는 다익스트라를 이용하여 구현한 코드이다.

첫번째 코드

from collections import deque
import sys
input = sys.stdin.readline

n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n + 1)]

for _ in range(m):
  a, b = map(int, input().split())
  graph[a].append(b)

dist = [-1] * (n + 1)
dist[x] = 0

q = deque([x])
while q:
  now = q.popleft()
  for next_node in graph[now]:
    if dist[next_node] == -1:
      dist[next_node] = dist[now] + 1
      q.append(next_node)

check = False
for i in range(1, n + 1):
  if dist[i] == k:
    print(i)
    check = True

if check == False:
  print(-1)

두번째 코드

from collections import deque
import sys
input = sys.stdin.readline

n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n + 1)]
dist = [0] * (n+1)
visited = [False] * (n + 1)

for _ in range(m):
  a, b = map(int, input().split())
  graph[a].append(b)

def bfs(x):
  res = []
  q = deque([x])
  visited[x] = True
  dist[x] = 0
  while q:
    now = q.popleft()
    for i in graph[now]:
      if not visited[i]:
        visited[i] = True
        q.append(i)
        dist[i] = dist[now] + 1
        if dist[i] == k:
          res.append(i)
  if len(res) == 0:
    print(-1)
  else:
    res.sort()
    for i in res:
      print(i, end='\n')

bfs(x)

기본적으로 처음에 내가 떠올린 방식과 비슷하게 구현했다. 차이점은 출력문이다. 나는 별도의 리스트에 k의 값이 존재하지 않으면 -1을 출력하도록 하였다. 첫번째 코드는 check 변수를 만들어 해당 변수가 False이면 -1이 출력되도록 했고, 두번째 코드는 도시 방문시 k의 값과 일치하면 정답 리스트에 추가한 후 정답 리스트에 값이 존재하지 않다면 -1이 출력되도록 했다. 

다익스트라

import sys
import heapq

input = sys.stdin.readline
INF = int(1e9)

n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n + 1)]
distance = [INF] * (n + 1)

for _ in range(m):
  a, b = map(int, input().split())
  graph[a].append((b, 1))


def dijkstra(start):
  q = []
  heapq.heappush(q, (0, start))
  distance[start] = 0

  while q:
    dist, now = heapq.heappop(q)
    # distance의 초기값이 INF이기 때문에 당연히 dist보다 작고,
    # 설령 이미 값이 존재한다고 해도 dist보다 작으면 갱신할 필요가 없다.
    if distance[now] < dist: continue
    for j in graph[now]:
      cost = dist + j[1]
      if cost < distance[j[0]]:
        distance[j[0]] = cost
        heapq.heappush(q, (cost, j[0]))


dijkstra(x)
answer = []
for i in range(1, n + 1):
  if distance[i] == k:
    answer.append(i)

if len(answer) == 0: print(-1)
else:
  for i in answer:
    print(i, end='\n')

다익스트라는 노드간의 거리가 가장 짧은 길을 찾는 알고리즘이다. 따라서 해당 문제에 적합한 알고리즘이라 볼 수 있는 것이다.

다익스트라 구현 방법에는 이중 반복문과 우선순위 큐를 이용한 두 가지 방법이 있는데, 우선순위 큐를 사용했을 때 시간 복잡도가 O(ElogV)로 훨씬 빠르게 작동하기 때문에 해당 코드를 우선순위 큐를 사용하여 구현하였다.

 

시간과 효율적인 측면에서는 내가 구현한 코드보다 첫번째와 두번째코드가 더 간결하고 더 빠르다. 아직 효율적이게 짜는 실력은 부족한거 같지만 옛날보다 발전한 점은 이제 머리속으로 생각한 내용을 코드로 옮기는데 걸리는 시간이 줄었다는 점이다. 또한 BFS로 구현할때 굉장히 익숙해진 느낌이 든다. 이처럼 조금씩 실력이 늘고 있으니 꾸준히 문제를 풀고 정리하면서 실력을 늘려나가야 되겠다.