BFS (5) 썸네일형 리스트형 백준 2644 촌수계산 - bfs에서 메모리초과가 안뜨게 하려면? 문제 링크 www.acmicpc.net/problem/2644 풀이 아이디어 최단거리 문제니까 당연히 dfs가 아닌 bfs를 이용해서 푸는 것이다. 노드번호와 cost의 쌍을 큐에 넣고 bfs돌리면 쉽게 풀 수 있다. 문제는 메모리! 아래 주석 친 부분에 처음에 if-return문을 넣었다가 메모리 초과가 떴었다. BFS 조건 판단은 반드시 방문여부 체크한 후에 하기!! 코드 #include using namespace std; vector tree[101]; bool visited[101]; int bfs(int a, int b){ queue q; q.push({a,0}); visited[a]=true; while(!q.empty()){ int front = q.front().first; int cos.. 백준 3055 탈출 - 확산하는 물체가 2개 있을때 bfs를 돌려야 한다면? 문제 링크 www.acmicpc.net/problem/3055 풀이 아이디어 최단경로 문제이므로 당연히 BFS를 이용해서 풀어야 한다. 문제는 확산하는 물체가 고슴도치 1개와 물 n개라는 것이다. 구체적으로 푸는 방식은 여러개가 있을 수 있다. 나는 bfs 함수를 하나만 정의했지만 물이 이동하는 bfs, 고슴도치가 이동하는 bfs 함수를 각각 짜서 비교해보며 진행을 해도 된다. 하지만 각 객체(고슴도치,물) 이 확산하는 정보는 따로 관리가 들어가야 하므로 queue는 2개를 반드시 이용해 주어야 한다. 나는 queue 2개를 이용을 하되, 함수를 하나만 정의 했다. 문제의 조건에 따라 물을 먼저 이동시키고, 그 이후에 고슴도치를 이동시키기. 추가적으로 사용한 2가지 팁은 1. for문을 이용해 큐의 사이.. 백준 14226 이모티콘 - 2차원 배열로 상태저장 bfs - c++ 링크 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다. 화면에 있는 이모티콘 중 하나를 삭제한다. 모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용 www.acmicpc.net 아이디어 오랜만에 bfs관련 풀어본 문제. 이문제는 주의해야 할점이, 클립보드에 복사한 이모티콘 갯수는 몇번이고 재사용이 가능하.. 백준 1261 알고스팟: bfs와 caching 쓰는 문제 c++ https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다. www.acmicpc.net 사실 이 문제는 분류가 다익스트라 알고리즘으로 분류되어있었는데, 그 알고리즘에 대해서 몰라도 풀수 있다. 전형적인 bfs문제는 아니고 다이나믹 프로그래밍의 캐시 개념만 조금 쓰면 풀 수 있다. 어떻게 보면 최단 경로 문제이기 때문에 (빙빙 돌아가면서 벽을 부숴가면서 미로를 탐색하진 않을것 아닌가?) bfs를 쓰는 것은 당연한 .. 백준 1697 숨바꼭질 - bfs - c++ https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 www.acmicpc.net 한 7번;; 만에 풀었다. 큐에다가 bfs를 진행하면서 넣고 빼고를 반복하면서 카운팅만 잘 해주면 풀 수 있는 문제지만 따져야 되는 조건들.. 이전 1 다음