펭로그

문제링크 : https://noj.am/16236 BFS로 그냥 풀면 간단한 문제일 줄 알았는데 개인적으로는 약간 고민을 많이 했던 문제이다.아기 상어가 물고기를 먹을 때 먹을 수 있는 물고기 중에서 가장 가까운 아무거나 먹는게 아니라 가장 위, 가장 왼쪽에 있는 것을 먹어야 한다는 까다로운 조건이 붙기 때문이다.이를 해결하기 위하여 우선순위 큐 + BFS를 사용하여 해결하였다. BFS를 위해 필요한 큐를 우선순위 큐로 사용하였고큐에 담길 데이터는 연산자 오버로딩을 통하여 아래와 같이 min heap이 구성되는 방식이다.① BFS 레벨이 작은 순서 (상어의 이동 거리)② x의 좌표가 작은 순서③ y의 좌표가 작은 순서 123456789101112131415161718192021222324252627282..

문제링크 : https://noj.am/16234 완탐 + DFS/BFS 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102 // BOJ 16234 인구 이동#include #include using namespace std; int dx[] = {0, 0, -1, 1};int dy[] = {-1, 1, 0, 0}; struct node { int x, y;}; int N; // 크기int L, R; //..

문제링크 : https://noj.am/6603 N개의 원소를 가지는 집합에서 K개를 고르는 조합(Combination) 문제로 STL의 permutation을 사용하면 쉽게 풀 수 있다.algorithm 헤더에 있는 next_permutation()과 prev_permutation()으로 순열을 구할 수 있다.[1, 2, 3, 4]를 next_permutation()을 사용하면[1, 2, 4, 3] [1, 3, 2, 4] [1, 3, 4, 2] [1, 4, 2, 3] ..... 이런 식으로 사전 순서대로 순열이 적용된다.prev_permutation()은 그 반대라고 볼 수 있다. 그렇다면 조합을 사용하려면 어떻게 해야할까?[1, 1, 0, 0]을 prev_permutation()으로 돌려보면 아래와 ..

문제링크 : https://noj.am/2583 단순 DFS/BFS 문제이다.계산하기 편하게 (1,1)~(N,M)의 영역을 사용한다.초기에 테두리를 방문한 것으로 체크하고 내부를 미방문한 상태로 초기화 시키면 ▣ Y >> X >> K; // true : 방문, false : 미방문 // 테두리를 방문한 것으로 만들고 내부는 미방문 상태로 초기화 arr = vector(X + 2, vector(Y + 2, true)); for (int i = 1; i > y1 >> x2 >> y2; for (int x = x1 + 1; x

문제링크 : https://noj.am/11403 전형적인 BFS / DFS 문제그냥 풀면 된다. 자기 자신노드로 돌아오는 경우가 있기 때문에 맨 처음은 방문체크를 하지 않았다.인접리스트는 graph[0] = {1, 3, 5, 6, 7} 이런 형태로 저장된다. 현재 노드에서 해당 노드로 갈 수 있으면 저장된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253// BOJ 11403 경로 찾기#include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cou..

문제링크 : https://boj.kr/11559 1. 블럭은 4개 이상 모였을 때 터짐2. 동시에 터지는 것은 하나의 연쇄 단계임3. 한 연쇄 단계에 블럭이 터진 이후 중력에 의해 블럭이 아래로 내려감 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124// BOJ 11559 Puyo Pu..

문제링크 : https://boj.kr/3055 BFS를 이용하여 풀이한 시뮬레이션 문제이다.다른 사람들 이야기를 들어보면 굳이 BFS를 이용하고 풀지 않아도 되는 것 같다.(물이 차오르는 시간들을 저장한 배열을 따로 만들면 되는듯 하다.) 아무튼 이 풀이는 BFS!! BFS로 풀이를 고려한다면1. 고슴도치가 비버굴을 찾기 위한 BFS2. 물이 차오르는 BFS동시에 2개의 BFS를 돌려야 한다. 하지만, 문제의 조건에서 '고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다.'라고 하였기 때문에물이 차오르는 BFS를 먼저 선행하고 고슴도치의 BFS를 후행하는 식으로 돌리면 된다.그렇게 하기 위해선 같은 큐 안에 '물'을 먼저 넣어서 돌리고 '고슴도치'를 뒤이어서 넣으면 된다. 입력시 물일 경우 큐에 넣고 고..

문제링크 : https://boj.kr/7562 (시작점) -> (끝점)까지 나이트가 갈 수 있는 경로의 최단거리를 구하는 문제로 이동 가능한 8방향으로 BFS를 돌리면 풀 수 있다.장애물 없이 오로지 도달만 하면 되기 때문에 방문 체크를 위한 배열 visited만 선언해주었다.방문 조건은 (0,0) ~ (len-1, len-1)의 범위로만 한정하였다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960// BOJ 7562 나이트의 이동#include #include #include using namespace std; const int dx[] = {-2,..

문제 링크 : https://boj.kr/2178 지난번에 풀었던 BOJ 7576 토마토 문제보다 훨씬 쉬운 BFS 문제인듯 하다.토마토 문제에서 잡았던 대부분의 기본 개념을 그대로 가지고 풀었다.토마토 보다 이 문제를 더 먼저 풀었으면 좋았을걸.. 먼저 이 문제는 입력 자료형이 공백으로 구분지어져있지 않기 때문에 1. std::istringstream 를 split 하여 입력받기2. char형 그대로 입력 받는 방법3. 스트링 클래스의 getline(std::cin, input); 사용4. scanf("%1d", &input); 처럼 형식지정자로 1자리만 받도록 하기등등 다양한 방법을 활용하여 입력 받아야 한다. 이 외에도 getch나 gets 등등 아주 많다.scanf를 사용하는게 제일 편하긴 하지만..

문제 링크 : https://boj.kr/7576 이 문제보다 기본 개념의 문제는 BOJ 2178 미로 탐색을 참고 컨셉을 잡는 데에 상당히 어려울 수 있지만 알고보면 기본적인 BFS 문제인 것 같다.map을 int형 컨테이너로 하나 만들어 입력 정보를 받고 이 정보를 visited로 사용하면 된다.현재 탐색하는 위치 정보는 별도의 구조체를 만들어 여기에 x, y 좌표와 BFS 탐색의 몇번째 단계에 해당하는지 level 변수를 추가하였다.입력 받을 때 익은 토마토를 발견하면 그 즉시 바로 큐에 담는다.큐에 담긴 순서대로 BFS를 수행하면 문제가 쉽게 풀리게 된다.BFS를 다 수행한 이후엔 다시 한번 전수조사를 해서 안익은 토마토를 체크했다. 12345678910111213141516171819202122..