공부하고 기록하는, 경제학과 출신 개발자의 노트

프로그래밍/코딩테스트 문제풀이

[Python] 프로그래머스. 버스 여행 (Level 4)

inspirit941 2019. 12. 21. 18:19
반응형

그래프에서, 연결할 수 있는 점을 전부 연결하는 형태의 문제.

bfs나 dfs 중 어느 것을 써도 해결 가능하며, 나는 bfs로 풀었다.

 

효율성 통과조건이 꽤 빡세게 설정되어 있는 것 같았다. visited를 2D List 대신 set으로 구현하니 풀렸다.

 

from collections import defaultdict, deque
def can_reach(start, des, table):
visited = set()
queue = deque()
queue.append(start)
while queue:
nxt = queue.popleft()
visited.add(nxt)
for i in table[nxt]:
# 목적지와 일치하는 경우
if i == des:
return 1
elif i not in visited:
queue.append(i)
visited.add(i)
# 도착할 수 없는 경우
return 0
def solution(n,signs):
table = defaultdict(set)
for y in range(n):
for x in range(n):
if signs[y][x] == 1:
table[y].add(x)
answer = [[0 for _ in range(n)] for _ in range(n)]
for y in range(n):
for x in range(n):
# y에서 x까지 도착할 수 있는지 검사한다.
answer[y][x] = can_reach(y, x, table)
return answer
반응형