0=2

문제https://www.acmicpc.net/problem/11559 문제 이해뿌요뿌요 게임 중, 현재 주어진 필드에서 몇연쇄가 되는지 구한다. 뿌요뿌요 룰- 뿌요의 색은 R, G, B, Y가 있다.- 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 그 뿌요들이 모두 없어진다. 이것을 1연쇄라고 한다.- 뿌요는 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다. 뿌요가 없어지면, 똑같이 아래로 떨어진다.- 아래로 떨어지고 나서 다시 뿌요가 터지면 1연쇄가 늘어난다.🚨 터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터진다. 여러 그룹이 터지더라도 1연쇄가 추가된다. 문제 풀이🔍 접근연결된 같은 색의 뿌요를 찾는다는 관점에서 DFS, BFS 탐색을 떠올릴 수 있다.탐색 후 연결된 뿌요..

문제https://www.acmicpc.net/problem/2606 문제 이해컴퓨터가 바이러스에 걸리면, 그 컴퓨터와 네트워크 상에서 서로 연결되어 있는 컴퓨터는 모두 바이러스에 걸린다.1번 컴퓨터를 통해 바이러스에 걸리게 되는 컴퓨터의 수 출력 문제 풀이 🔍 접근 네트워크 상에서 연결되어 있는 컴퓨터들을 그래프로 나타낼 수 있다.1번 컴퓨터와 연결된 모든 컴퓨터를 탐색한다. 💡 DFS & BFS인접 행렬에 네트워크 상에서 서로 연결되어 있는 컴퓨터의 정보를 저장한다.1번 컴퓨터부터 탐색을 시작해서, 1번 컴퓨터와 연결된 모든 컴퓨터에 방문한다.방문할 때마다 방문 표시를 하고 카운트(바이러스에 걸리는 컴퓨터의 수)를 증가시킨다. 코드1️⃣ DFS#include #include using namesp..

문제https://www.acmicpc.net/problem/1303 문제 이해N × M 전쟁터에서 우리 병사(W)의 위력의 합과 적국의 병사(B)의 위력의 합을 구한다.N명이 뭉쳐있을 때 N²의 위력을 낼 수 있다. 문제 풀이💡 DFS & BFS첫 번째 칸부터 dr, dc 배열을 이용해서 같은 문자('W' / 'B')가 있는 곳을 상하좌우로 탐색한다.이미 방문한 곳은 탐색하지 않는다.탐색하는 곳은 방문 표기하고, 해당 병사 수 카운트를 증가시킨다.탐색을 종료한 후 뭉쳐있는 병사의 위력을 저장한다.병사의 위력을 합한 값을 각각 출력한다. 코드1️⃣ DFS#include #include #include using namespace std;int n, m, cnt;char color;vector> boar..

문제https://www.acmicpc.net/problem/1890 문제 이해수가 적혀 있는 N×N 게임판에서 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 따라 점프한다.규칙에 맞게 이동할 수 있는 경로의 개수를 구한다. 규칙각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다.0은 종착점을 의미한다.현재 칸에 적혀있는 수만큼 오른쪽이나 아래로만 이동 가능하다.한 번 점프할 때 방향을 바꿀 수 없다. 오른쪽으로 또는 아래로 점프를 하는 두 경우만 존재한다. 문제 풀이 🔍 접근 각 칸마다 현재 칸까지의 경로의 개수를 저장한다. 💡 Dynamic Programming칸에 적힌 수만큼 이동해서 해당 칸까지의 경로의 개수를 저장한다.첫 번째 칸(경로의 개수 1)부터 시작한다.오른쪽으로 ..

문제https://www.acmicpc.net/problem/2579 문제 이해점수가 쓰여 있는 계단을 밟는 게임에서 얻을 수 있는 총 점수의 최댓값을 구한다. 계단 오르는 규칙한 번에 한 계단 또는 두 계단씩 오를 수 있다.연속된 세 계단을 밟으면 안 된다.마지막 도착 계단은 반드시 밟아야 한다.시작점은 계단에 포함되지 않는다. 문제 풀이 🔍 접근 각 계단마다 현재 계단까지의 점수 최댓값을 구해서 저장한다. 💡 Dynamic Programming각 계단은 1칸 또는 2칸 전 계단에서 온 것이므로 max(1칸 전 최댓값, 2칸 전 최댓값) + 현재 계단 점수로 식을 세울 수 있다.하지만 연속 세 칸을 밟으면 안 되는 조건을 만족하지 못한다.이 조건을 고려해서 경우의 수를 생각해보면 아래와 같이 나타낼..

문제https://www.acmicpc.net/problem/1260 문제 이해그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과 출력 문제 풀이주어진 간선과 두 정점의 번호를 이용해 인접 행렬을 저장한다. 💡 DFS현재 정점과 연결된 정점을 순서대로 재귀 탐색한다.시작 V → V와 연결된 정점 A → A와 연결된 정점 B → B와 연결된 정점 C ..인접 행렬 adj[cur][1 ~ n] 순회. 연결되어 있으면 dfs(next)dfs 탐색하면서 방문 표시 & 출력 배열에 삽입하기이미 방문한 곳이면 return💡 BFS현재 정점과 연결된 정점을 모두 큐에 삽입하고 큐에서 정점을 꺼내면서 탐색한다.시작 V → V와 연결된 정점 A → V와 연결된 정점 B → …A와 연결된 정점 A’ → A’와 연결된..

문제https://www.acmicpc.net/problem/2667 문제 이해N × N 크기의 정사각형 지도에서 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다.집이 있는 곳(1)끼리 상하좌우로 연결시켜 단지를 만든다.총 단지수와 단지내 집의 수를 오름차순으로 출력한다. 문제 풀이 🔍 접근 집이 존재하는 곳을 기준으로 그 집의 상하좌우에 또 다른 집이 존재하는지를 판단하는 그래프 탐색 문제로 볼 수 있다.지도를 순회하면서 '1'이 나왔을 때 모든 인접 정점을 방문하여 연결된 집의 개수를 구한다. 🔨 구현 BFS와 DFS를 이용하여 풀 수 있다.방문 표기는 visited 배열을 만드는 대신 지도에서 방문한 곳을 '0'으로 바꾸어 표기할 수 있다.집이 있는 곳에서 dr, dc 배열을 이용해서 상..

문제https://www.acmicpc.net/problem/3085 문제 이해N×N 크기의 보드에 사탕을 4가지 색으로 채워져있다.인접한 두 칸을 골라 사탕을 서로 교환한다.행 또는 열에서 같은 색으로 이루어져 있는 가장 긴 연속 부분을 구한다. 문제 풀이 🔍 접근 모든 경우의 수를 탐색하는 시간복잡도를 계산해보면,사탕을 교환하는 데 N * N, 연속하는 최대 개수를 구하는 데 N * N 이므로 총 O(N^4)이다.N ≤ 50이므로 제한시간 내에 계산할 수 있다. 💡 브루트포스행/열에서 인접한 두 칸을 골라 서로 사탕을 교환한다.연속하는 행/열의 최대 개수를 찾는다.1회 교환할 때마다 최대 개수를 찾는다. 코드#include #include using namespace std;/*1. 행/열에서 인..

문제https://www.acmicpc.net/problem/1789 문제 이해서로 다른 N개의 자연수의 합이 S이다. S가 주어질 때 N의 최댓값을 구한다. 문제 풀이💡 아이디어N이 최대가 되려면, 자연수를 1부터 차례대로 더하는 방식을 생각할 수 있다. 1 + 2 + 3 + 4 + ... = S 이런식으로 더할 경우 N이 최대가 된다.1 + 2+ 3 + ... + n = n * (n + 1) / 2 인 점을 이용해서 예시를 살펴볼 수 있다.예: 2001 + 2 + 3 + ... + 18 + 19 = 190 에서 10을 더하면, 서로 다른 수라는 조건을 만족하지 못한다.1 + 2 + 3 + ... + 17 + 18 = 171 이므로, 29를 더하면 200이 된다.N의 최댓값은 19이다. 🔨 구현반복..

문제https://www.acmicpc.net/problem/15650 문제 이해1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 출력한다.고른 수열은 오름차순이어야 한다. 문제 풀이💡 DFS를 이용한 백트래킹 이전에 올린 N과 M (1) 문제에서, 출력할 수열이 오름차순인 것만 추가되었다. [BOJ][C++] 백준 15649번: N과 M (1)문제https://www.acmicpc.net/problem/15649 문제 이해1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구한다. 문제 풀이💡DFS를 이용한 백트래킹    1부터 N까지 재귀함수를 이용해 탐색하y-e-99.tistory.comN과 M (1)과 풀이 방식이 비슷한데, for 반복문에서 i값을 이용하면 중복없이 오름..