유령이 나오는 젤리하우스

Algorithm/Baekjoon

[BOJ 16236][백준 16236번] 아기상어 (파이썬 풀이)

https://www.acmicpc.net/problem/16236 🤔 문제 설명 및 입출력 ✍ 접근 방법 문제의 핵심은 "상어가 먹을 수 있는 물고기 중 가장 가까운 물고기를 찾아라" 이다. "가장 가까운 대상 찾기 + 입력이 행렬 꼴 " 이면 대부분의 문제는 BFS를 활용하여 풀이한다. 얼핏 보면 문제에 조건이 엄청 바리바리 달려있어서 복잡해보이지만, 상어의 크기가 커지는건 크게 어려운 부분이 아니라, 주어진 입력에 대해 다음 시퀀스를 반복하면 된다. 잡아먹을 수 있는 물고기를 찾는다 찾은 물고기들 중 가장 가까운 놈들 잡아먹는다 행렬을 갱신한다. ( 잡아 먹은놈 행렬에서 삭제) 크기를 키울 수 있으면 키운다 더 이상 잡아 먹을 수 없을 때까지 반복한다. 여기서 포인트는 잡아먹을 수 있는 "물고기 중..

Algorithm/Baekjoon

[BOJ 1865][백준 1865번] 웜홀 (파이썬 풀이)

https://www.acmicpc.net/problem/1865 🤔 문제 설명 및 입출력 ✍ 접근 방법 음수 가중치가 들어가는 그래프 탐색 문제이다 ➡ 벨만-포드 알고리즘을 적용해서 풀자. 사실 이렇게 알고리즘을 뭔가 공식화해서 풀어재끼는게 썩 유쾌하지는 않지만, 그래도 코딩 테스트를 염두해보았을 때,머리 속을 스쳐지나가는 생각들을 단숨에 훅 잡아채는게 유리하다는 생각이 든다. 하지만, 이 문제는 시작점에서 도착점까지의 최소 경로비용을 구하는 순수 벨만-포드 문제가 아니다. 문제의 요지는 백준이가 시간이 줄어들면서, 출발 위치로 돌아오는 것이 가능한지를 물어보기 때문에, 우리는 주어진 그래프에서 벨만-포드 알고리즘이 무한히 반복되는 경우 ( 음수 사이클에 빠지는 경우)를 찾아야한다. 그럼 그 음수 사이..