본문 바로가기

Algorithm283

[BOJ]2146번: 다리 만들기(py) www.acmicpc.net/problem/2146 BFS 문제입니다. N제한이 100이므로 BFS로 전체 그래프를 한 번 탐색하는데 O(100*100)이 걸립니다. 그러므로 BFS를 딱 한 번만 돌아서 모든 섬간의 최소 거리를 구해줘야합니다. (시간초과 X) 1. 섬을 컴포넌트 별로 나눕니다. 2. 컴포넌트 별로 나눈 모든 섬들의 좌표를 큐에 넣습니다. 3. 섬 = '방문한 칸', 바다 = '방문하지 않은 칸'이라는 의미로 BFS를 돕니다. 4. 서로 다른 컴포넌트인 두 섬이 BFS로 영역을 확장하다 만나면 그 둘이 지나온 거리를 더하면 정답입니다. 무슨 말인지 이해가 잘 안가신다면 아래 코드를 참고하시면 됩니다. 코드: github.com/cotchan/algorithm/blob/main/python.. 2021. 2. 5.
[BOJ]17142번: 연구소3(py) www.acmicpc.net/problem/17142 시뮬레이션 문제입니다. n개의 바이러스 위치 중에 m개를 뽑아서 최소를 찾는 문제이므로 조합(combination)을 통해 해결할 수 있습니다. 한 가지 주의 사항은 바이러스의 종류와 무관하게 빈 칸(0)만 채우면 됩니다. 그러므로 탐색을 종료 조건은 BFS로 채운 빈 칸의 숫자가 주어진 입력의 0칸 갯수와 동일하면 됩니다. 코드: github.com/cotchan/algorithm/blob/main/python/BOJ/BOJ17142.py 2021. 2. 3.
[BOJ]1956번: 운동 www.acmicpc.net/problem/1956 플로이드 알고리즘을 통해 해결할 수 있습니다. 코드: github.com/cottory/algorithm/blob/master/JAVA/BOJ1956.java 2020. 11. 10.
[BOJ]16918번: 봄버맨 www.acmicpc.net/problem/16918 시뮬레이션 문제입니다. 매 초가 지날 때 마다 3, 4번에 해당하는 로직을 처리해주면 됩니다. 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다. 1초가 지난 후에 3초 전에 설치된 폭탄이 모두 폭발한다. 단, 문제에 명확히 나와있지 않은 한 가지 조건은, 연쇄 폭발이 일어날 때 3초가 지난 폭탄 좌표를 모두 기억해놓고 그 좌표로부터 4방향 탐색을 모두 실시해줘야 한다는 점입니다. 즉, (0,0)부터 (N,N)까지 순차적으로 그냥 3초 지난 칸에서 4방향 다 터트리는 식으로 하면 일부 칸에서 연쇄 폭발이 안 일어나도 잘못된 답이 출력될 수 있다는 얘기입니다. 코드: github.com/cottory/algorithm/blob/master/JAVA/.. 2020. 11. 4.

티스토리툴바