이세계개발자의 개발일지

이번 문제는 1926번 그림이문제 요약세로 x, 가로 y 크기의 2차원 격자에서 값이 1인 칸들을 상하좌우로 연결된 묶음(연결요소)으로 정의한다. 그림(연결요소)의 총 개수와가장 큰 그림의 넓이(포함 칸 수)를 계산하여 출력해야 함접근법모든 칸을 순회하면서 값이 1이고 아직 방문하지 않은 시작점을 발견할 때마다 BFS를 수행하여 해당 연결요소 전체를 탐색한다 BFS 과정에서 방문할 때마다 면적 변수를 1씩 증가시키고, 탐색 종료 시 최대 넓이를 갱신한다. 각 칸은 최대 한 번만 방문하므로 전체 시간 복잡도는 O(x⋅y)가 된다 알고리즘 설계입력으로 x,y 및 x×y 격자를 수신방문 배열을 초기화이중 반복으로 모든 좌표 (i,j)(i, j)(i,j)를 순회graph[i][j]==1 이고 미방문이면, 해당 ..

이번 문제는 트리의 부모 찾기이다문제 요약정점 1을 루트(root) 로 하는 트리가 주어진다. 각 간선은 무방향이며, 정점 수는 N, 간선 수는 N-1목표는 정점 2부터 N까지 각각의 부모 정점을 출력하는 것이다 접근법트리는 연결되어 있고 사이클이 없다 루트(1)에서 한 번 BFS(또는 DFS) 를 돌면서 “처음 방문”한 정점의 부모를 누가 찍었는지 기록하면 끝시작: 1을 큐에 넣고 시작인접 정점 v를 처음 만났다면 parent[v] = u큐가 빌 때까지 반복 → parent[2..N] 출력시간 복잡도는 인접 리스트 기준으로 O(N)이다 작성코드아래 코드는 BFS로 부모를 구한다. 입력 이후 인접 리스트를 정렬해(선택 사항) 작은 번호부터 탐색하도록 했다#include using namespace std..

이번 문제는 1189번 컴백홈이다문제 요약지도는 R × C 크기의 격자각 칸은 빈 칸(.) 또는 장애물(T)시작점: 왼쪽 아래 (R-1, 0)도착점: 오른쪽 위 (0, C-1)이동은 상하좌우로만 가능같은 칸을 두 번 방문할 수 없음정확히 K 칸을 지나 도착해야 함접근법DFS (깊이 우선 탐색)현재 위치에서 상하좌우 탐색장애물이거나 방문한 적 있는 칸은 무시이동 거리를 하나씩 늘려가며 탐색거리가 K가 되었을 때 도착점에 있다면 경우의 수 +1백트래킹 (방문 표시 후 해제)방문 여부를 체크하면서 DFS 실행탐색 후에는 방문 해제(visited[nx][ny] = false)해서 다른 경로도 탐색 가능하게 함좌표계 처리 주의입력은 R행 × C열본 코드는 graph[C][R] 구조 (열, 행 순서)로 관리작성코드..

이번 문제는 2583번 영역 구하기다문제 설명크기가 M × N인 2차원 평면이 있고 이 평면에 직사각형 K개가 주어지며, 각 직사각형 영역은 색칠되어 있다고 가정합니다.색칠된 부분을 제외한 나머지 빈 칸들이 몇 개의 분리된 영역을 이루는지, 그리고 각 영역의 넓이를 구하는 문제다출력:영역의 개수각 영역의 넓이(오름차순)접근법그래프 초기화graph[y][x] 형태로 M×N 크기의 2차원 bool 배열을 만든다직사각형이 주어지면 해당 구역을 true(막힘)로 표시한다DFS 탐색아직 방문하지 않았고(!visited), 색칠되지 않은(!graph) 좌표에서 DFS를 시작DFS를 통해 상하좌우로 인접한 빈 칸을 모두 탐색하며 영역의 넓이를 계산결과 저장탐색이 끝날 때마다 영역 개수를 +1 하고, 해당 영역 넓이를..

이번 문제는 1325번 효율적인 해킹이다문제 설명N개의 컴퓨터와 M개의 단방향 신뢰 관계가 주어짐A B라는 입력은 B 컴퓨터가 A 컴퓨터를 신뢰한다는 뜻한 컴퓨터를 해킹하면, 그 컴퓨터를 신뢰하는 컴퓨터도 해킹 가능가장 많은 컴퓨터를 해킹할 수 있는 시작 컴퓨터 번호를 모두 출력해야 함문제 접근단방향 간선이 주어지고, 한 노드에서 시작해 도달 가능한 모든 노드를 세는 문제이므로 DFS 또는 BFS로 해결할 수 있다A B가 주어졌을 때, B → A 방향으로 그래프를 구성해야 함이유: B를 해킹하면 A도 해킹 가능하기 때문각 노드를 시작점으로 DFS를 실행해 몇 개의 노드를 해킹할 수 있는지 계산가장 많이 해킹할 수 있는 노드의 번호를 출력 작성코드#include using namespace std;int ..

이번 문제는 전쟁 - 전투다문제 설명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..