뿌요뿌요라는 게임을 들어보았을지 모르겠지만, 뿌요뿌요는 그림으로 봐도 알 수 있듯이 일본의 SEGA사에서 만든 게임이고 테트리스 처럼 여러 색깔과 모양의 블럭들이 내려와서 바닥이나 제일 위에 있는 블럭과 맞닿았을 때 그 상태에서 상하좌우로 4개의 같은 색깔의 모양이 위치하게 되면 그 블럭들이 터지면서 점수가 오르는 게임이다. 블럭이 터지게 되면 위에 있는 블럭들이 아래의 빈 공간을 메꾸기 위해 내려오게 되고 그 과정에서 새롭게 4개의 블럭이 생기면 연쇄적으로 터질 수 있다.따라서 이 문제에서도 이 게임의 방식과 동일하게 구현을 하면 된다.출처https://www.acmicpc.net/problem/11559풀이BFS를 이용하는데, 블럭이 모여서 터지게 되면 중력의 영향을 받아서 터진 블럭 위에 있는 블럭..

출처https://www.acmicpc.net/problem/2573풀이 전략[백준 2636 - 치즈] https://www.acmicpc.net/problem/26362024.09.10 - [Baekjoon] - [C++] 백준 2636 - 치즈 [Gold4] [C++] 백준 2636 - 치즈 [Gold4]출처https://www.acmicpc.net/problem/2636풀이 전략먼저 문제 해석을 해보면, 1로 입력 받은 치즈가 시간이 지날 수록 녹아 내리는데, 녹아 내리는 부분을 보면 공기(0)과 맞닿아 있는 부분이라는 것을 알phj6724.tistory.com이 문제와 상당히 유사한 방식으로 접근을 해야 한다.다만 다른 점은, 이 문제에서는 빙산이 둘로 쪼개지는 순간의 시간을 출력해야 하기 때문에..

출처https://www.acmicpc.net/problem/1922풀이 전략문제에서 Minimum Spanning Tree 알고리즘을 사용하라고 힌트를 줬기 때문에 Prim 알고리즘이나 Kruskal 알고리즘을 사용하여 풀이를 할 것이다.Prim보다는 Kruskal이 구현이 약간?은 더 간단할 것 같아서 Kruskal 알고리즘으로 풀었다.Pseudo Code풀이수도 코드에서 보면 알겠지만, Kruskal Algorithm의 특징은 Union-Find를 사용한다는 점과 edge를 weight가 작은 순으로 정렬해서 최솟값을 찾는다는 점이다. 그렇기 때문에 위의 그림과 같은 순서가 나온다.다만, 5번째의 경우 weight가 8인 edge가 4-6과 5-6 둘 다 가능한데, 문제 힌트에서 4-6이라고 주어져..

출처https://www.acmicpc.net/problem/1504풀이 전략Dijkstra 알고리즘을 이용하여 최단경로를 구할 것이다. 다만, 이 문제의 경우 마지막에 입력 받는 v1과 v2를 무조건적으로 거친 경로 중 최단 경로를 찾는 것이기 때문에 세 가지 경우로 나누어서 구할 것이다.from 1번 (시작 정점) to v1from v1 to v2from v2 to N번 (도착 정점)세 가지의 경우로 나눈 최단 경로를 모두 더해주면 정답이 구해질 것이라고 생각하고 문제를 접근했다풀이문제의 예시를 그림으로 그려보면 위의 그림과 같다. 첫번째 예시를 보면 2-3을 지나는 최단경로를 찾으면 1-2-3-4로 총 합은 7이 된다. 이 경우, 모든 vertex가 연결되어 있기 때문에 인접노드행렬을 그려보면 IN..

출처https://www.acmicpc.net/problem/2636풀이 전략먼저 문제 해석을 해보면, 1로 입력 받은 치즈가 시간이 지날 수록 녹아 내리는데, 녹아 내리는 부분을 보면 공기(0)과 맞닿아 있는 부분이라는 것을 알 수 있다. 그렇기 때문에 먼저 BFS로 0인 부분을 탐색해서 방문처리를 한 다음, 4방향 탐색을 이용하여 0 다음 노드가 1인 부분을 찾아서 그 부분을 cheese라고 처리를 한 뒤 0으로 바꿔서 그 다음 탐색에서는 그 부분이 공기라고 인식할 수 있도록 바꾸는 전략을 이용하였다.풀이소스 코드/*# Question: BJ 2636 (https://www.acmicpc.net/problem/2636)# Rank : Gold4# Algorithm : Graph, BFS, Simula..

출처https://www.acmicpc.net/problem/2583풀이 전략이 문제는 BFS로 풀면 되지만, 한 가지 까다로운 점은 Array의 index로 접근을 할 수 있지만 Array의 index는 좌상단에서 우하단 방향으로 커지는 반면 XY좌표계는 좌하단에서 우상단으로 커지기 때문에 Array로 계산을 할 때 XY 좌표계로 변환을 해주고 구해야 한다.이 점을 제외하면 무난무난한 문제이기 때문에 구하면 된다.풀이위의 풀이에 대해 설명을 하자면,빨간 형광펜으로 칠한 부분이 문제에서 예시로 주어진 부분이고, 빨간 점이 입력 값의 좌표(XY 좌표계), 배열 내부에 파란 색으로 적은 숫자가 배열의 index이다.빨간 점(X,Y)과 배열의 index를 비교해서 관계식을 찾는 것이 첫 번째 목표이다.따라서 ..