반응형


그래프에서, 연결할 수 있는 점을 전부 연결하는 형태의 문제.
bfs나 dfs 중 어느 것을 써도 해결 가능하며, 나는 bfs로 풀었다.
효율성 통과조건이 꽤 빡세게 설정되어 있는 것 같았다. visited를 2D List 대신 set으로 구현하니 풀렸다.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
반응형
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
[Python] 백준 1495. 기타리스트 (0) | 2019.12.23 |
---|---|
[Python] 백준 11053. 가장 긴 증가하는 부분 수열 (LIS) (0) | 2019.12.22 |
[Python] 백준 12865. 평범한 배낭 (0) | 2019.12.20 |
[Python] 백준 7569. 토마토 (0) | 2019.12.19 |
[Python] 프로그래머스. 2018 카카오 recruit - 뉴스 클러스터링 (0) | 2019.12.18 |