hades

🥅 문제https://www.acmicpc.net/problem/16928 🔍 설계주사위를 던져서 이동하는데, 이동한 칸이 사다리면, 사다리를 타고 위로 올라간다. 뱀이 있는 칸에 도착하면, 뱀을 따라서 내려가게 된다. 올라간다는 것은 현재 위치한 칸보다 번호가 큰 칸으로 이동한다는 것이고, 내려간다는 것은 현재 위치한 칸보다 번호가 작은 칸으로 이동한다는 것이다. 주의헤야할 것은 사다리나 뱀을 만나면 무조건 이용해야 하고, 한 칸에 사다리가 있거나, 뱀이 있거나, 비어있다는 것이다. 출발지인 1에서 목적지인 100까지 이동하기 위해, '사다리는 높은 번호의 칸으로 이동시켜 때문에 사다리만 사용하면 좋은 것 아닌가? '라는 생각을 할 수 있지만, 무조건 사다리만 이용해야만 좋은 결과가 나오리라는 보장..

🥅 문제https://www.acmicpc.net/problem/16236 🔍 설계초기 설계에서는 초를 늘리면서, 거리가 동일할 때는 위, 왼쪽, 오른쪽, 아래 순으로 우선순위가 높으므로, 탐색 순서도 위, 왼쪽, 오른쪽, 아래 순으로 탐색한다.  먹을 수 있는 것이 있으면, 바로 먹고, 거리를 반환한다. 먹을 수 없으면, 거리를 갱신하고, 큐에 담는다. 반환된 거리가 0이 아니면, 먹을 수 있는 것이 있다는 의미이므로, 최종 결과에 더한다.반환된 거리가 0이면 먹을 수 있는 것이 더 이상 없다는 의미이므로 반복문을 종료한다.#include #include #include #include using namespace std;int n, baby_shark_size = 2, eat_count = 0, ..

🥅 문제https://www.acmicpc.net/problem/2638 🔍 설계치즈가 닿아있는 블럭이 2개 이상이면 녹을 예정이다. 치즈 내부에 있는 공기는 치즈에 영향을 줄 수 없다. 모눈종이의 맨 가장자리들은 치즈가 놓이지 않는다고 했으므로, 그 중 대표적인 (0, 0) 에서 시작하여 외부 공기의 영향력을 행사한다.  외부 공기의 영향력을 행사하는 방법은 BFS를 이용하여 치즈가 놓인 곳에 2번 방문했을 때, 1시간 후에 녹으면서 새롭게 영향력을 행사할 수 있는 외부 공기 후보들의 모임인 next_q에 추가하는 것이다. 만약 next_q에 아무것도 추가되지 않는다면 그대로 종료되고, 추가된 것이 있다면 1초를 증가시킨다. next_q에 추가하는 이유는 치즈가 녹는 과정은 1시간 후에 동시에 이루..

🥅 문제https://www.acmicpc.net/problem/11724 🔍 설계서로소 집합을 사용하여 연결된 것들끼리 그룹을 형성하게 한다.  그룹의 수는 맨 꼭대기에 있는 조상의 수이다. 문제 입력 순서에 따라 parent[x]가 맨 꼭대기 조상이 아닐 수 있으므로, find_parent(x)로 맨 꼭대기 조상을 집합에 삽입한다. BFS로 방문처리를 하여 영역의 개수를 구하여 해결할 수도 있다. 👊 풀이1#include #include #include #include using namespace std;int n, m, u, v;vector parent(1001);set result;int find_parent(int x) { if (parent[x] != x) { return find_pa..

🥅 문제https://www.acmicpc.net/problem/10026 🔍 설계상하좌우로 인접한 영역 중 같은 색을 가진다면 한 구역으로 인식한다는 것에서 BFS임을 알아차릴 수 있다. 적록색약인 사람과 적록색약이 아닌 사람의 경우를 나누어서 BFS를 수행한다. 적록색약이 아니라면, BFS가 시작되는 지점의 색깔과 같아야 한 구역에 포함되고, 적록색약이라면 시작되는 지점의 색깔이 빨간색 또는 초록색이면, 이웃한 지점의 색깔도 빨간색 또는 초록색이면 한 구역에 포함되고, 파란색의면 이웃한 지점의 색깔도 파란색이어야 한다. 👊 풀이#include #include #include using namespace std;int n;vector> painting1(100, vector(100));vector..

🥅 문제https://www.acmicpc.net/problem/7569 🔍 설계익은 토마토가 인접한 익지 않은 토마토에 영향을 준다. BFS 문제라는 것을 알아차릴 수 있다. 처음에 익은 토마토를 큐에 담는다. 날마다 익은 토마토의 영향력을 행사한다. 주변의 토마토가 익지 않은 토마토라면, 익게 만들고, 그 토마토를 큐에 담는다. 주의해야할 것은 날마다 익은 토마토의 영향력을 행사했는데, 영향을 받은 토마토가 없다면, day를 증가시키면 안된다. 👊 풀이#include #include using namespace std;int dh[] = { -1,1,0,0,0,0 };int dl[] = { 0,0,0,0, -1,1 };int dw[] = { 0,0,-1,1,0,0 };int m, n, h, da..

🥅 문제https://www.acmicpc.net/problem/2667 🔍 설계1로 구성된 칸들이 서로 연결된 것을 하나의 단지라고 한다는 것에서 BFS임을 알아차릴 수 있다. 지도의 칸에 대하여 반복문을 수행하고, 1인 칸이 있으면, 그 칸이 단지를 구성하는 시작점이다. 따라서, 단지 개수를 1 증가시키고, BFS를 실행하여 단지를 구성하고 넓이를 반환한다. 반환한 넓이는 오름차순 우선순위 큐에 담아 출력하였다. 👊 풀이#include #include #include #include using namespace std;int dx[] = {-1,1,0,0};int dy[] = {0,0,-1,1};int n, count = 0;string row;vector> mapp(25, vector(25))..

🥅 문제https://www.acmicpc.net/problem/2606 🔍 설계1번과 연결된 컴퓨터들이 감염된다는 것에서 BFS를 활용해야 한다는 것을 알 수 있다. 방문 처리를 하여 중복해서 큐에 담지 않도록 설계하였다. 👊 풀이#include #include #include #include #include using namespace std; int n, m, a, b, result=0;vector> adj_list(101);vector visited(101);queue q;void bfs(){ visited[1] = true; q.push(1); while (!q.empty()){ int x = q.front(); q.pop(); for (int i=0; i> n >> m; for (i..

🥅 문제https://www.acmicpc.net/problem/2178 🔍 설계미로가 주어지고, 1인 칸 중에서 인접한 칸으로 이동할 수 있다는 것에서 BFS라는 것을 파악했다. 지나야하는 최소 칸을 구해야 하기 때문에, 각 칸마다 그 칸으로 오기까지 이동한 총 칸의 수를 dp에 저장한다. 어떤 칸으로 이동했을 때, 이동하기 전 칸이 저장한 값+1이 이동한 칸까지 이동한 총 칸의 수이다. 이 값보다 이미 저장하고 있는 값이 작다면, 최소 칸을 구할 수 없으므로, 큐에 담지 않는다. 👊 풀이#include #include #include #include #include using namespace std; int n, m;int dx[] = {-1,1,0,0};int dy[] = {0,0,-1,1}..

🥅 문제https://www.acmicpc.net/problem/1697 🔍 설계현재 위치를 x라고 할 때, 그 위치에서 +1, -1, *2의 위치로 이동할 수 있으므로, 큐에서 현재 위치를 꺼내 매 초마다 이동할 수 있는 새로운 위치를 갱신한다.   큐가 빌 때까지 하는데, 어떤 초에 놓여져 있는 위치로부터 다음 초에 이동할 위치 얻어내는 과정에서 이동하기 전 size를 저장하고, 반복문을 사용하였다.  다음 초에 이동할 수 있는 위치의 범위를 반드시 확인해야 한다.  어떤 위치에 이미 이동했고, 그로 인해 새로운 위치를 얻어냈는데, 나중에 또 방문한다면 중복이 일어나 메모리 초과, 시간 초과가 발생하므로 어떤 위치에 이동한 시각을 visited에 저장하여 저장된 시각보다 도착한 시각이 크다면 큐에..