BOJ (4) 썸네일형 리스트형 [C++/11559] puyo puyo - using simulation 11559 puyo puyo https://www.acmicpc.net/problem/11559 solution 전형적인 시뮬레이션 문제이다. 여기서 포인트는 어떻게 "아래로 떨어짐"을 구현하는가 이다. 아래로 떨어지는 걸 구현하기 위해서는 가장 밑에 있는 뿌요가 없애야 하는 것인지 아닌지에 따라 다르다. 만약 가장 밑에 있는 뿌요가 없어져야 한다면 위에서부터 한칸씩 내려오면서 값을 덮어씌우고 마지막에 맨 첫 줄의 뿌요 값을 . 으로 교체해주면 된다. 알고리즘은 다음과 같다. 1. 현재 필드 값을 보고 BFS를 돌려 인접한 색의 개수가 4개인 그룹을 찾는다. 2. 이 그룹의 값들은 없어져야 하기 때문에 이를 표시하기 위해 좌표를 저장했다가 * 으로 바꾼다. 3. 없어져야 하는 값들에 대해서 for문을 돌.. [C++/14502] 연구소 - using BFS 문제: 연구소 아이디어: BFS 전형적인 BFS 문제다. [특정 map에서 무언가가 퍼져나가는 경우의 수 or 시간 or 집합의 수] 등등의 대부분은 BFS/DFS로 해결 가능하다. 이 문제의 핵심은 어떻게 3개의 벽을 세울 수 있는 경우의 수를 계산하느냐에 달려있다. 나의 경우에는 3개의 벽을 세울 수 있는 모든 가능한 경우의 수를 계산했다. 벽은 빈칸에만 세울 수 있고 어떻게 벽을 세울 때 best 결과가 나올지 모르기 때문에 full search를 하도록 했다. 왜냐하면 애초에 제한 사항에 다음과 같이 map의 크기가 8x8이 최대이기 때문에 가능한 모든 경우의 수를 세어도 무방했다. 다음 로직에 따라 알고리즘을 구성했다. 1. map에서 모든 칸을 확인하며 빈칸일 때 3개의 벽을 세울 수 있는 경.. [C++/16236] 아기 상어 - using BFS 문제 아이디어: BFS 가장 가까운 물고기부터 먹어야 하기 때문에 물고기까지의 최단 거리중 가장 짧은 물고기를 먹을 수 있는지 아닌지 체크하면서 물고기를 차례대로 확인하면 된다. 구현 // 46: 아기 상어 (삼성 기출) #include #include #include #include using namespace std; // 북 서 남 동 int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -1, 0, 1}; // n(공간의 크기) int n; int weight = 2; // 거리 테이블 int dist[20][20]; void BFS(vector &v, int i, int j) { queue q; dist[i][j] = 0; q.push({i, j}); while (!q.e.. [C++/7576] 토마토 - using BFS 문제 아이디어: BFS 진짜 전형적인 BFS 응용 문제이다. 토마토가 익는 시간을 함께 queue에 넣어서 저장한 다음, 익는 시간이 특정 시간을 지나고 나면 하루가 지난 것으로 판별해야 한다. 또한 맨 처음에 queue에 넣는 좌표는 토마토가 있는 좌표를 모두 넣는다. 이때 시간대는 모두 0으로 초기화 한다. 토마토가 이동할 수 있는 동서남북 4 방향에 대해서 토마토가 없는 경우에 값을 바꾸고 queue에 넣어준다. 이때는 (이전시간 + 1)로 설정하여서 넣어준다. 구현 #include #include #include #include using namespace std; int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; int m, n; int graph[.. 이전 1 다음
