yeony's story

전형적인 bfs 함수 문제! 문제에서 주어진 예제의 맵은 아래와 같다. 0은 벽, 1은 상어 이 문제에서 원하는 것은 안전거리가 가장 큰 칸을 구하는 것 안전거리가 무엇을 의미하느냐! 해당 칸과 가장 가까이 있는 아기 상어와의 거리를 의미한다. 상어가 1마리면 구하기 쉬웠을 텐데 상어가 여러마리 존재하니까 그걸 어떻게 해결해야 하느냐가 관건이었던 문제다. bfs를 이용하여 처음에 상어의 위치들을 먼저 큐에 넣고 시작한다. (1,3) (3,1) (5,4) 를 각각 큐에 먼저 넣는다. 그리고 나서 (1,3) 위치에 있는 상어 주변 8방향을 살펴보고 0인 곳은 array[1][3]+1을 더해준 값을 넣어준다. 0이 아니면 패쓰! 이런식으로 하면 된다! (간단) dfs로 풀 수 없는 이유는 상어가 여러 마리 존..

오랜만에 bfs 문제를 접했다..! 역시나 오늘도 헤맸다 !.! 문제 해석하기 1 4 2 2 1 (시작점 idx 2 ) 2 -> 왼쪽 1 o -> 오른쪽 4 o -> x -> 오른쪽 1 o -> 왼쪽 2 o -> 왼쪽 4 o o의 개수 = 5개 from collections import deque n = int(input()) array = list(map(int, input().split())) start = int(input()) - 1 visited = [0] * n result = 0 def bfs(start): # start=idx global result queue = deque() queue.append(start) visited[start] = 1 result+=1 while queue: ..

(처음 든 생각) BFS 같다.. 느낌이 1번 도시에서 2번, 3번 도시를 가야하고? 2번 도시에서 갈 수 있는 곳이 있는지, 조건을 부합하는 지 확인한 뒤 3번 도시도 확인해야 하니까!! (처음 푼 풀이) : BFS 처음에 이 문제도 EOFError를 사용해야 하는 줄 알고 좀 헤맸다. 문제 좀 잘 읽어볼 것.. BFS 알고리즘이니까, 큐를 이용해서 풀어야한다. 위 예제를 생각해보면, k=2 이다. (거리정보) 1번 도시에서 갈 수 있는 도시는 2번, 3번 따라서 큐에 2번, 3번을 넣고 방문처리를 해준다. 이때 방문처리 리스트를 통해 답을 구할 것이다. 처음엔 set()을 이용했는데, 시간초과가 떠서 ㅠㅠ popleft로 큐에서 데이터를 꺼내온다. (2번) 2번에서 갈 수 있는 도시는 3번, 4번 하..