BFS22 [백준] 6593번 - 상범 빌딩 (C++) 문제 및 풀이 문제) 백준 - BFS - 상범빌딩 https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 3차원 미로를 탈출할 수 있는 최단 시간을 찾는 문제였습니다. 그래프 탐색에서 최단 시간을 찾을 때, 간선의 비용이 같으면 BFS를 사용합니다. 기본적인 3차원 BFS를 연습하기에 좋은 문제였습니다. C++ 소스 코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%205000~99.. 2022. 1. 6. [백준] 17471번 - 게리맨더링 (파이썬) 문제 및 풀이 문제) 백준 - BFS - 게리맨더링 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 삼성 기출스러운 조합+그래프 탐색 문제였습니다. 조합을 사용할 때, 파이썬 itertools에 내장된 combinations만큼 편한 게 없기 때문에 파이썬의 해결했습니다. N개의 구역 중에 1부터 N//2 구역을 뽑은 후 BFS를 통해 인구 수와 방문한 구역 수를 반환합니다. 마찬가지로, 위에서 뽑은 구역을 제외한 나머지 구역에 대해 인구 수와 구역 수를 계산하여 이전에 계산한 .. 2022. 1. 4. [백준] 2251번 - 물통 (C++) 문제 및 풀이 문제) 백준 - BFS - 물통 https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net a, b, c의 양을 bfs를 통해 탐색합니다. 모든 경우(물 옮겨 담기)를 시행하면서, a가 0일 경우 임의의 배열에 담아 결과를 출력합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201000~4999/2251_%EB%AC%BC%ED.. 2021. 12. 31. [백준] 13549번 - 숨바꼭질 3 (C++) 문제 및 풀이 문제) 백준 - BFS - 숨바꼭질 3 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 순간 이동하는 경우에 드는 비용이 없으므로, 움직이는 방법에 대해 우선순위를 매겨야 합니다. 우선순위 큐(priority queue)를 이용하여 움직이는 최소 시간이 적은 것부터 방문하게 하며, 순간이동은 비용이 들지 않으므로 걷는 것보다 먼저 방문합니다. C++ 소스코드) Full Code) https://github.co.. 2021. 12. 28. [백준] 2636번 - 치즈 (C++) 문제 및 풀이 문제) 백준 - BFS - 치즈 https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net BFS로 board에서 치즈 개수를 탐색하며 0으로 바꿉니다. prevCheeze로 이전 치즈의 개수를 저장하고 cntCheeze가 0이면 break 합니다. C++ 풀이) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201000~4999/2636_%EC%B9%98%EC%A6%88.cpp GitHu.. 2021. 12. 23. [백준] 13913번 숨바꼭질 4 (C++) 문제 및 풀이 문제) 백준 - BFS - 숨바꼭질 4 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS를 통해 탐색하면서 동생의 위치를 찾는 문제였습니다. tr 배열을 이용해 방문했던 이전 점의 좌표를 저장했습니다. 그 후 반복문을 통해 이동한 자취를 출력했습니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201.. 2021. 12. 14. [백준] 9019번 - DSLR (Python) 문제 및 풀이 문제) 백준 - BFS - DSLR https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 만들 수 있는 수 중에서 최소 명령을 사용하는 것을 탐색하는 문제였습니다. BFS로 탐색하면서 queue에 (숫자, 명령어)를 넣고 명령어를 만들 수 있는 모든 경우의 수(D, S, L, R)를 탐색했습니다. 파이썬 소스 코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Pr.. 2021. 12. 10. [프로그래머스] 코딩테스트 고득점 Kit - 단어 변환 (Python) 문제 및 풀이 문제) 프로그래머스 - BFS - 단어 변환 https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 단어별로 개수를 저장하기 위해 파이썬의 자료구조인 딕셔너리를 사용했습니다. 딕셔너리를 모두 0으로 초기화하여 방문 여부를 판단했습니다. BFS를 통해 탐색하면서 target이 나올 때 결괏값을 return 합니다. Python 소스 코드) Full Code) https://g.. 2021. 12. 7. [백준] 5014번 - 스타트링크 (C++) 문제 및 풀이 문제) 백준 - BFS - 스타트링크 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net BFS를 통해서 G층까지 최소 버튼 횟수를 구한다. 핵심은 Queue에 방문 층과 버튼 횟수를 함께 넣는 것. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%205000~9999/5014_%EC%8A%A4%ED%83%80%ED%8A%B8%EB%A7%81%ED%81%AC... 2021. 11. 9. 이전 1 2 3 다음 반응형
