이세계개발자의 개발일지

이번 문제는 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으로..