18352.md

백준 18352번 특정 거리의 도시 찾기

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

---

코드 설명

• 노드들의 연결된 모습을 저장할 곳으로 dictionary로 정했다. 단방향이기 때문에 입력받은 순으로 첫번째 노드를 key로, 두번째 노드를 value에 리스트 형식으로 넣었다.
• bfs를 통해 탐색했으며, q에서 pop한 노드를 출발노드로 지정해 key값으로 이용, 방문하지 않았을 경우 value의 리스트들을 q에 넣음과 동시에 visited이란 리스트에 거리를 저장했다.

소스코드

• 메모리 : 115124 KB
• 시간 : 2724 ms

from collections import deque
import sys

def bfs(start):
	q = deque()
	q.append(start)
	while q:
		s = q.popleft()
		lst = grid[s]
		for l in lst:
			if not visited[l]:
				q.append(l)
				visited[l] = visited[s]+1
	
	

n, m, k, x = tuple(map(int, sys.stdin.readline().split()))
grid = {}
for num in range(1,n+1):
	grid[num] = []

for _ in range(m):
	n1, n2 = tuple(map(int, sys.stdin.readline().split()))
	grid[n1].append(n2)

visited = [0]*(n+1)

bfs(x)

for v in range(n+1):
	if visited[v] == k and v != x:
		print(v)

visited[x] = 0

if k not in visited:
	print(-1)

오답 노트

• 초반에는 grid를 dictionary로 하지 않고 이차원 리스트로 했으나 메모리 초과가 나 dictionary로 바꿨다.
• grid를 while q 안에 for문을 이용해 일일히 검사하는 과정을 거쳤더니 시간 초과가 나서, 무조건 연결된 노드들만 확인하기 위해 dictionary의 value를 연결된 리스트로 만들어 시간을 단축했다.
• 입력도 input에서 sys.stdin.readline()으로 바꿔 조금이나마 시간을 아낄 수 있도록 했다.

오답 코드(메모리초과)

from collections import deque
import sys

def bfs(start):
	q = deque()
	q.append(start)
	while q:
		s = q.popleft()
		for g in range(n+1):
			if grid[s][g] == 1 and not visited[g]:
				q.append(g)
				visited[g] = visited[s]+1
	
	

n, m, k, x = tuple(map(int, sys.stdin.readline().split()))
grid = [[0]*(n+1) for _ in range(n+1)]
for _ in range(m):
	n1, n2 = tuple(map(int, sys.stdin.readline().split()))
	grid[n1][n2] = 1

visited = [0]*(n+1)

bfs(x)

for v in range(n+1):
	if visited[v] == k and v != x:
		print(v)

visited[x] = 0

if k not in visited:
	print(-1)

오답 코드(시간초과)

from collections import deque

def bfs(start):
	q = deque()
	q.append(start)
	while q:
		s = q.popleft()
		for g in grid:
			if s == g[0] and not visited[g[1]]:
				q.append(g[1])
				visited[g[1]] = visited[g[0]]+1
				
			elif s == g[1] and not visited[g[0]]:
				q.append(g[0])
				visited[g[0]] = visited[g[1]]+1
	
	

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

bfs(x)

for v in range(n+1):
	if visited[v] == k and v != x:
		print(v)

visited[x] = 0

if k not in visited:
	print(-1)