[백준] 5014 스타트링크(Python)

백준 - 5014 스타트링크

풀이

bfs
visited 배열을 따로 두지 않고, 기존의 graph배열을 사용해서 0인 경우=방문하지 않은 경우 로 보고 활용했다.

문제에 작성된 예시도 되고, 질문하기에 있는 반례도 거의 되는데 왜 실패가 뜨는 지 모르겠다ㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏ
다른 사람들이 올린 코드와 비교해봤을때, visited 배열이 없는 차이밖에 모르겠는데.....
근데 나는 graph로 해줬는데!!!!!!!!!

아무리봐도 잘 모르겠다...... 헬프미🫠

(+수정)

visited를 따로 만들어주고 시작점을 방문했다고 표시하고 돌리니까 통과했다......
처음 시작점을 방문하지 않았다고 판단해서 다시 돌게 되는 게 문제였던 것 같다.............
visited를 따로 만들 필요성을 못 느꼈었는데, 다시 공부하게 되는 시점이다.......

맨 처음 시작점을 방문했다고 해야하는 경우 무조건 visited 만들어버리기.. 메모...

(++++수정2)
생각해보니 visited를 따로 만들지 않고도 수정할 수 있다..
pos가 시작점이 아닐때만 queue에 넣어주면 되잖아.................................

bfs->while->for->if문 조건에 pos != s(시작점) 만 넣어주면 된다.....(황당)

이걸 몰라서 고민한 나........ 눈물 광광 엔딩

---

코드

❗️실패

from sys import stdin
from collections import deque

MAX = 1000000

def bfs():
	queue = deque([s])
	while queue:
		vertex = queue.popleft()
		if vertex == g:
			return graph[g]
		for pos in [vertex + u, vertex - d]:
			if 0 < pos <= MAX and not graph[pos]:
				graph[pos] = graph[vertex] + 1
				queue.append(pos)
	return -1

f, s, g, u, d = map(int, stdin.readline().split())
graph = [0] * (MAX + 1)

answer = bfs()
print(answer if answer != -1 else 'use the stairs')

성공 with visited

from sys import stdin
from collections import deque

def bfs():
	queue = deque([s])
	visited[s] = 1
	while queue:
		vertex = queue.popleft()
		if vertex == g:
			return graph[g]
		for pos in [vertex + u, vertex - d]:
			if 0 < pos <= f and not visited[pos]:
				visited[pos] = 1
				graph[pos] = graph[vertex] + 1
				queue.append(pos)
	return -1

f, s, g, u, d = map(int, stdin.readline().split())
graph = [0] * (f + 1)
visited = [0] * (f + 1)

answer = bfs()
print(answer if answer != -1 else 'use the stairs')

성공 without visited

from sys import stdin
from collections import deque

def bfs():
	queue = deque([s])
	visited[s] = 1
	while queue:
		vertex = queue.popleft()
		if vertex == g:
			return graph[g]
		for pos in [vertex + u, vertex - d]:
			if 0 < pos <= f and not visited[pos] and pos != s:
				visited[pos] = 1
				graph[pos] = graph[vertex] + 1
				queue.append(pos)
	return -1

f, s, g, u, d = map(int, stdin.readline().split())
graph = [0] * (f + 1)
visited = [0] * (f + 1)

answer = bfs()
print(answer if answer != -1 else 'use the stairs')

---

눈물의 제출 기록.......