본문 바로가기
728x90

BFS50

[python] 백준 21609 상어 중학교 https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 문제 해결 놓치기 쉬운 조건들을 먼저 잘 인지하고 있어야한다. 블록 그룹은 연결된 블록 집합이며 일반 블록이 적어도 한개 이상 있어야하며 색은 모두 같아야한다.(무지개는 무조건 포함가능) 연결된 블록이 가장 많은 블록 집합을 골라야한다. 만약 같은 것이 존재한다면 무지개색이 가장 많은 것을 선택하며 그래도 같으면 기준 블록 행이 가장 큰 것, 그래도 같으면 기준 블록 열이 가장 큰 것을 고르는.. 2023. 7. 8.
[python] 백준 11967 불켜기 https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 문제 해결 BFS로 방을 움직이면서 불을 켜는 문제 첫 번째 문제는 A방에서 B방의 불을 켤 수 있다는 것이다.(이는 문제에서 주어진다.) 그러면 이동하면서 A방에서 킬 수 있는 불은 모두 켜야한다. ( (i,j)위치의 방에 불이 켜지면 값이 0→1로 바뀌는 것으로 구현) 두 번째 문제는 조건부로 동,서,남,북 중 방에 불이 켜져있는 방향으로만.. 2023. 7. 3.
[python] 백준 5214 환승 https://www.acmicpc.net/problem/5214 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 문제 해결 BFS를 이용하면 쉽게 풀릴 것 같은 느낌이 든다. 문제는 하이퍼튜브로 두개의 역만 묶는 것이 아나리 두 개 이상의 역이 묶일 수 있다는 것이다. 그리고 메모리를 신경써야한다. BFS를 돌 때 역마다 방문했는지 체크하는 것이 아니라 어떤 하이퍼튜브를 이용했는가도 고려대상이 된다. 문제 해결 from collections import deque def bfs().. 2023. 6. 30.
[python] 백준 9328 열쇠 https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 문제 해결 주어진 열쇠를 찾고 열쇠에 맞는 문을 열어 최대한 많은 문서를 찾는 문제 움직임을 보면 bfs를 이용하는 것이 편할 것 같다. 하지만 갔던 길을 또 갈 수 있으므로 갔던 길을 체크하는 visited를 성과가 있을 때마다 리셋을 시켜줘야한다. key의 유무를 dictionary를 통해 저장하면 좋을 것 같다. 한 번 얻은 문서는 다시 중복해서 먹을 수 없으므로 문서를 얻었으면 answer += 1을 .. 2023. 6. 22.
728x90