이세계개발자의 개발일지

이번 문제는 18352번 특정 거리의 도시 찾기이다문제 요약입력N(도시 수), M(도로 수), K(목표 거리), X(시작 도시)M개의 도로: a -> b (단방향)출력X로부터 최단거리가 정확히 K인 도시 번호들을 오름차순으로 출력없다면 -1접근 아이디어dist[v] = 시작점 X에서 v까지의 최단거리를 저장하는 BFS를 수행방문하지 않았던 정점만 방문(dist == -1)거리 갱신 직후 dist[next] == K이면 answer에 담아둔 후 최종적으로 answer를 정렬해 출력하면 끝작성코드#include using namespace std;int N,M,K,X;void BFS(vector> & city,vector & answer);int main (void){ cin >> N >> M >> K..

이번 문제는 14940번 쉬운 최단거리다문제 요약입력 격자: 0 = 벽(못 감), 1 = 지나갈 수 있음, 2 = 시작점출력 규칙:시작점은 0 (거리 0)갈 수 있는 칸은 최단거리도달 불가한 1은 -10은 그대로 0접근법각 칸을 정점, 4방향 인접 칸을 간선으로 보면 무가중치 그래프 최단거리 → BFS가 정답지도(graph) 자체를 거리 저장용으로 덮어쓰기시작점(2)은 0으로 바꾸고 시작이동 가능한 1만 큐에 넣으며 graph[nx][ny] = graph[cur] + 1로 거리 누적BFS 종료 후, 한 번도 방문 안 된 1을 -1로 치환복잡도시간: O(N*M) — 각 칸 최대 한 번씩 큐에 들어간다공간: O(N*M) — 방문배열 / 큐가 격자 크기와 같은 오더거리 배열 dist를 따로 만들지 않고, 한 ..

이번 문제는 5014번 스타트링크다문제 요약정점: 각 층 1..F간선: x → x+U, x → x-D (범위 밖은 무시)목표: 시작층 S에서 목표층 G까지 버튼 최소 횟수불가능: 도달 못하면 "use the stairs"접근법이동 비용이 모두 동일(버튼 1회)하므로 무가중치 최단거리 => BFS가 정답이다visited를 거리 배열로 사용해 -1(미방문), 0(시작), … 형태로 관리하면 오프바이원 실수를 예방할 수 있고, U==0 또는 D==0이라도 이미 방문한 층은 다시 넣지 않으므로 무한루프 없이 안전함시간복잡도: 각 층을 최대 한 번 방문 → O(F)공간복잡도: O(F)알고리즘 설계입력으로 F, S, G, U, D를 받는다크기 F+1의 거리배열 visited를 -1로 초기화 후, 시작층 S를 0으로..

이번 문제는 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 이고 미방문이면, 해당 ..

이번 문제는 7562번 나이트의 이동이다문제 요약체스판 한 변의 길이 I가 주어지고, 나이트의 시작 좌표 (x, y)와 목표 좌표 (nx, ny)가 주어진다나이트가 시작점에서 목표점까지 최소 몇 번 이동하면 도착하는지 출력테스트케이스가 여러 개 주어진다체스판 좌표는 0 ~ I-1 (열/행 헷갈리지 않게 한 가지 규칙으로만 쓰면 됨)나이트 이동: 8방향(-2,-1), (-2, 1), (-1,-2), (-1, 2), (1,-2), (1, 2), (2,-1), (2, 1)접근법이 문제는 간선 가중치가 모두 1인 격자 최단거리 문제 → BFS가 정석이다dist(혹은 방문 겸 거리 배열)를 -1로 초기화: 미방문 표기시작칸은 0으로 두고 큐에 넣는다큐를 돌며 현재 칸에서 나이트 이동 8방을 확장처음으로 목표칸을 ..

이번 문제는 트리의 부모 찾기이다문제 요약정점 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..

이번 문제는 16953번 A -> B 이다문제 요약허용 연산x → 2xx → 10x + 1목표: A에서 시작해 B에 도달하는 최소 단계 수 + 1을 출력 (도달 불가 시 -1)접근법BFS(너비 우선 탐색)시작값 A를 루트로 상태를 확장합니다. 간선 가중치가 모두 1이므로, 처음 B를 만나는 순간의 레벨이 곧 정답이다상태: 현재 값 x간선: x → 2x, x → 10x + 1next > B는 확장할 필요가 없으므로 가지치기방문/거리 관리는 map(또는 unordered_map)으로 처리(참고) 역방향 그리디(B → A) 도 매우 간단하다 B의 끝이 1이면 /10, 아니고 짝수면 /2, 그 외는 실패작성코드#include using namespace std;int BFS(long long a, long l..

이번 문제는 13913번 숨바꼭질 4이다문제 요약N에서 K로 이동할 때 가능한 연산은 x-1, x+1, x*2.모든 연산 비용이 1이므로 가중치가 없는 그래프의 최단거리 문제이고, 정석은 BFS이다 접근법BFS(너비 우선 탐색): 시작점 N에서 한 단계씩 확장하면, 처음 K를 만나는 순간의 깊이가 곧 최단 시간방문 체크: 큐에 삽입(push)할 때 visited[next]=true로 표시해 중복 탐색 방지부모 추적(parent 배열): parent[next] = x로 “어디서 왔는지” 기록해 두고, K를 찾으면 parent를 거슬러 올라가 경로를 복원경로 정방향으로 출력: 역추적은 K → … → N이므로 reverse로 뒤집어 N → … → K로 출력작성코드#include using namespace s..

이번 문제는 13549번 숨바꼭질 3이다문제 요약수빈이는 현재 위치 N, 동생은 위치 K에 있고 수빈이가 이동할 수 있는 방법은 세 가지다X - 1 (1초 소요)X + 1 (1초 소요)X * 2 (0초 소요)즉, 간선의 가중치가 0 또는 1인 그래프 최단거리 문제인데 일반 BFS로는 가중치 차이를 반영할 수 없기 때문에, 덱을 이용한 0-1 BFS가 필요합니다. 덱(deque)Double Ended Queue의 줄임말 → “앞뒤 양쪽에서 넣고 뺄 수 있는 큐”std::deque 로 C++ STL에서 제공특징:push_front() / pop_front() → 앞에서 삽입·삭제push_back() / pop_back() → 뒤에서 삽입·삭제즉, 스택(stack)과 큐(queue)의 장점을 합쳐 놓은 자료구..

이번 문제는 12851번 숨바꼭질 2이다.문제 요약수빈이는 위치 N, 동생은 위치 K에 있다수빈이는 1초마다 다음 세 가지 행동 중 하나를 할 수 있음X - 1 로 이동X + 1 로 이동X × 2 로 순간이동문제는 수빈이가 동생을 찾는 데 걸리는 최소 시간 & 최소 시간으로 도달하는 경우의 수 출력문제 설계노드 = 위치(0 ~ 100000)간선 = 한 번의 이동(X-1, X+1, X*2)이동 시간은 모두 1초 → BFS(너비 우선 탐색) 으로 해결 가능distance[pos] : 시작점에서 pos까지의 최단 시간way[pos] : 시작점에서 pos까지 최단 시간으로 도달하는 경우의 수BFS 탐색 과정에서:처음 방문하는 경우 → 최단 시간 기록 + 경우의 수 전달이미 최단 시간으로 도달한 적 있음 → 경..