이세계개발자의 개발일지

이번 문제는 전쟁 - 전투다문제 설명N × M 크기의 전쟁터가 있다각 칸에는 아군(W) 또는 적군(B)이 배치되어 있고,같은 진영이 상하좌우로 붙어 있으면 하나의 부대로 취급한부대 전투력 = (부대 인원 수)^2아군과 적군의 총 전투력을 각각 계산접근 방법1. 문제 구조 분석입력에서 N(가로, 열), M(세로, 행)이 주어진다전쟁터를 M행 × N열의 2차원 배열로 저장각 칸에서 DFS를 사용하여 같은 진영의 연결된 모든 칸 탐색.방문할 때마다 인원 수(count_parts)를 1씩 증가.탐색이 끝나면 (count_parts)^2를 해당 진영의 전투력에 더함.2. DFS 탐색상하좌우 이동을 위해 fourway_x와 fourway_y 방향 배열 사용.방문한 칸은 visited 배열에 체크.경계 체크 시 0 ..

이번 문제는 2468번 안전 구역이다문제 개요문제 링크: 백준 2468번 - 안전 영역N×N 크기의 지도에서 각 칸의 높이는 0 이상 100 이하비가 내리면 일정 높이 이하의 영역은 물에 잠기게 되고, 물에 잠기지 않는 영역들을 안전 영역으로 정의하고비가 내린 후, 각 높이에 대해 물에 잠기지 않는 영역의 개수를 구하는 문제이다.접근법이 문제는 각 높이별로 물에 잠기지 않는 영역을 찾아 그 개수를 계산하는 문제다.단지의 개수를 세는 알고리즘을 사용하여, 각 높이에 대해 안전 영역을 구하는 방식으로 접근하였다입력 받기N×N 크기의 지도와 각 칸의 높이를 입력함각 높이에 대해 안전 영역 개수 계산각 높이에 대해 해당 높이보다 작은 값은 물에 잠기므로, 그 높이 이상인 부분만 연결된 안전 영역으로 취급DFS를..

이번 문제는 2667번 단지번호붙이기 문제다문제 개요문제 : 백준 2667번 0과 1로 이루어진 N×N 크기의 지도에서 1은 집이 있는 곳, 0은 집이 없는 곳서로 인접한 집들이 모여 하나의 단지를 형성하며, 인접은 상하좌우로만 판정 목표단지의 개수 출력각 단지에 속하는 집의 수를 오름차순으로 출력접근법이 문제는 그래프 탐색 문제로, 2D 격자를 그래프로 보고 DFS(깊이 우선 탐색)로 해결하였다전체 지도(map)를 입력받아 저장.방문 여부를 체크할 visited 배열 준비.모든 좌표를 순회하며:방문하지 않았고 집(1)이 있다면 DFS 시작.DFS로 연결된 모든 집을 방문 처리하고 개수를 센 뒤 리스트에 저장.단지 개수 출력 후, 각 단지의 집 수를 오름차순으로 출력.작성코드#include using n..

이번 문제는 11724번 연결 요소의 개수다.문제 개요그래프 이론에서 Connected Component란, 서로 연결되어 있는 정점들의 집합을 의미한다백준 11724번에서는 주어진 무방향 그래프의 연결 요소 개수를 구해야 함 문제 조건입력첫 줄에 정점의 개수 N, 간선의 개수 M다음 M개의 줄에는 간선 정보 u v (u와 v는 연결된 정점)정점 번호는 1부터 N까지출력그래프의 연결 요소 개수접근법그래프 저장 방식vector>를 이용한 인접 리스트 방식방문 체크vector로 방문한 정점을 기록DFS 수행방문하지 않은 노드에서 DFS 시작 → 해당 노드와 연결된 모든 노드 방문DFS가 한 번 완료될 때마다 연결 요소 개수 +1결과 출력작성코드#include using namespace std;void DF..

이번 문제는 2963번 섬의 개수다.문제 개요문제: 백준 4963번 - 섬의 개수지도에서 섬(1)을 탐색하여 총 몇 개의 섬이 존재하는지를 구하는 문제섬은 가로, 세로, 대각선으로 연결된 모든 1들로 구성입력: 여러 테스트 케이스가 주어짐각 테스트 케이스마다 지도의 가로(h), 세로(w) 가 주어짐이후 w행 h열의 지도 정보가 입력됨1은 땅, 0은 바다대각선 포함 8방향 인접이면 같은 섬으로 간주입력의 끝은 0 0 (종료 조건)접근법 (DFS)전체 지도를 순회하면서방문하지 않은 땅(1)을 만나면 DFS로 연결된 모든 땅을 방문 처리DFS를 시작할 때마다 섬 개수(result)를 +1모든 좌표를 검사한 후 result 출력작성코드#include using namespace std;void DFS(vecto..

이번 문제는 2644번 촌수계산이다.문제 요약사람 수 n두 사람 start, end가 주어지고, 이 둘 사이의 촌수를 구하기이어서 m개의 관계 정보가 (a, b) 형태로 주어짐. 이는 a와 b가 서로 가족 관계라는 의미관계는 양방향접근 방식문제를 그래프로 생각하면 단순해진다. 사람은 정점(Node), 가족 관계는 간선(Edge)DFS를 이용해 start에서 출발해 end까지 탐색하고, 몇 단계(간선)를 거쳤는지를 세어주면 된다주의할 점DFS에서는 재귀 호출을 통해 깊이를 누적하는데, 정답을 못 찾고 돌아오는 경우에는 깊이를 되돌려야 한다이걸 백트래킹(backtracking)이라고 하며, 이번 문제의 핵심이다. 작성코드#include using namespace std;void DFS(int* start,..

이번 문제는 2606번 바이러스다.문제 개요컴퓨터가 네트워크로 연결되어 있을 때, 1번 컴퓨터가 바이러스에 걸렸을 경우 몇 대의 컴퓨터가 추가로 감염되는지를 구하는 문제입니다.모든 컴퓨터는 서로 직접 또는 간접적으로 연결되어 있을 수 있음입력으로 연결 관계가 주어지며, 양방향1번 컴퓨터가 바이러스에 감염될 때, 감염되는 컴퓨터 수(1번 제외)를 구해야 합니다.접근법이 문제는 DFS(깊이 우선 탐색) 또는 BFS(너비 우선 탐색)를 사용하여 1번 컴퓨터에서 시작해 연결된 모든 노드를 탐색하면 해결할 수 있습니다.이 글에서는 DFS를 사용함 방문한 노드를 기록할 visit_dfs 배열(또는 벡터)을 사용하여 중복 방문을 방지각 컴퓨터의 연결 정보를 저장하는 인접 리스트(벡터 배열)를 사용DFS로 재귀 호출하..

이번 문제는 1012번 유기농 배추 문제이다이분탐색 다음으로 도장깨기 중인 DFS BFS 유형 2번째 문제이다.문제 개요어떤 배추밭이 있다. 서로 인접한 배추들은 해충 방제를 위해 하나의 군락으로 취급된다.이 군락들을 하나씩 지켜줄 벌레가 최소 몇 마리 필요한지 구하는 문제다.배추는 2차원 좌표상에 심겨 있음상하좌우로 인접한 배추들은 하나의 군락떨어져 있는 배추 군락의 수를 구하면 곧 정답접근법 핵심 포인트이 문제는 2차원 배열에서 연결된 덩어리의 개수를 세는 문제다.DFS 또는 BFS로 풀 수 있으며, 여기서는 재귀 DFS를 사용한다.DFS로 접근하는 방법배추가 심어진 위치(arr[x][y] = true)를 입력으로 받는다.2차원 배열을 전부 순회하면서:배추가 있고 && 아직 방문하지 않았다면, DFS..

이번 문제는 1260번 DFS와 BFS 문제이다접근법 1. 그래프 표현인접 리스트 방식 사용 (vector v[1001])정점 번호가 1부터 시작하므로 1001 크기로 선언양방향 간선이므로 v[a].push_back(b)와 v[b].push_back(a) 모두 수행2. 방문 순서 정렬문제 조건에 따라 정점 번호가 작은 것부터 방문해야 하므로, 각 정점의 연결 리스트를 오름차순 정렬합니다 3. DFS 구현재귀 방식 사용방문 체크는 visit_dfs 배열로 관리방문한 정점은 result_dfs 벡터에 저장4. BFS 구현큐(queue) 사용방문 체크는 visit_bfs 배열로 관리방문한 정점은 result_bfs 벡터에 저장핵심 포인트그래프 탐색 문제에서는 방문 순서 조건을 항상 유의해야 합니다. 이 문제에..

이번 문제는 10189번 Hook 이다.작성코드#include using namespace std;int main(void){ ios::sync_with_stdio(false); cin.tie(0); cout