BFS28 [BOJ] 21609. 상어 중학교(Python) / Simulation 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 2021 상반기 삼성 SW역량테스트 기출문제이다. 이번에 출제된 4문제 중 내 기준 가장 까다롭고 시간이 많이 든 문제였다.. BFS의 효율을 높이기 위한 전략이 필요했다. 완전 구현 문제로 고도의 집중력을 발휘해야 한다. 특별히 사용한 알고리즘은 가장 큰 그룹 찾을 때와 이를 지울 때의 BFS 정도이고, 완전 구현 문제이다. 사용 알고리즘 : Simultaion (+ BFS) 사용 자료구조 : Max Heap(최대 힙) 1번 조건 - "크기가 가장 큰 블록 .. 2021. 5. 4. [BOJ] 1938. 통나무 옮기기(Python) / BFS 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 2021. 4. 11. [BOJ] 1525. 퍼즐(Python) / BFS 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 신박한 느낌의 BFS 문제였다. 처음 문제 봤을 때 감조차 잡히지 않았다. 이게 어떻게 BFS 인지 이해가 되지 않아, 코드 말고 아이디어 만이라도 얻어야겠다 싶어 구글링 해보니.. 3*3 맵에 있는 숫자들을 문자열로 변환해서 0이 있는 곳 기준으로 숫자 바꿀 수 있는 위치로 바꿔주고 BFS로 뻗어나가며 타겟 문자열을 찾는 방식으로 접근해야 한다는 것을 깨달았다. 이 아이디어를 바탕으로 코드를 짜봤다. # 아이디어 참고까지 30분, 문제 pass까지 1시간 30분/ 총 2시간 소요 사용 알고리즘 : BFS 최단 시간 알고리즘 3*3 맵의 .. 2021. 4. 11. [BOJ] 11967. 불 켜기(Python) / BFS 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 각 방에서 불을 켤 수 있는 곳의 위치가 주어지면 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다. 불을 켤 수 있는 방의 최대 개수를 구하는 문제이다. 사용 알고리즘 : BFS 너비 우선 탐색 근래 풀어본 BFS 문제 중에 내 기준 가장 까다로운 문제였다.. 처음에 쉬운 문제라고 생각했는데 하다보니 자꾸 꼬이고 잘 안 되어서 다른 분의 블로그를 참고했다. 코드를 .. 2021. 4. 9. [BOJ] 2234. 성곽(Python) / BFS 2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net # 1시간 40분 소요 사용 알고리즘 : BFS 너비 우선 탐색 문제 푸는 흐름은 아래 코드에 주석으로 잘 적어놨고, makeBinInfo() 함수 binInfo 딕셔너리에 0~16 숫자를 4자리 이진수로 변환한 정보를 담아줬다.(0: 나갈 수 있음, 1: 벽. 나갈 수 없음) checkRooms() 함수 visited 배열에 방의 번호를 적으며 bfs를 퍼트렸다. 이 때, 방 번호를 binInfo라는 딕셔너리를 활용해 현재 내 번호에 해당하는 남, 동, .. 2021. 4. 9. [BOJ] 2933. 미네랄(Python) / Simulation + BFS 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 동굴에 있는 미네랄의 모양과 두 사람이 던진 막대의 높이가 주어진다. 모든 막대를 던지고 난 이후에 미네랄 모양을 구하는 프로그램을 작성하는 문제 # 2시간 48분 소요 사용 알고리즘 : Simulation + BFS 구현이 상당히 까다로운 문제였다. 엣지 케이스가 많다.. 질문 게시판에 나온 모든 반례를 넣으며 코드를 고쳤고, 결국 pass! pass 후 거의 1-2시간을 더 투자해 최적화했고 시간 1위를 달성했다!(248ms, PyPy3 제출) 고려할 것이 많으므로 기능화.. 2021. 4. 9. 이전 1 2 3 4 5 다음
