cedis 님의 블로그

문제 요약항목설명입력정점 개수 N, 간선 개수 M, 시작 정점 V그래프양방향 그래프조건방문 가능한 정점이 여러 개면 번호가 작은 정점을 먼저 방문출력첫 줄은 DFS 방문 순서, 둘째 줄은 BFS 방문 순서문제에서 중요한 조건은 “방문할 수 있는 정점이 여러 개인 경우 번호가 작은 것을 먼저 방문한다”는 점입니다. 그래서 인접 리스트 정렬이 핵심입니다. [Source](https://www.acmicpc.net/problem/1260)이 문제의 핵심 개념1. DFS는 깊게 들어간다현재 갈 수 있는 정점이 있으면 끝까지 깊게 내려갑니다. 보통 재귀로 구현하면 자연스럽게 DFS 흐름이 만들어집니다.2. BFS는 가까운 정점부터 넓게 간다시작 정점에서 한 번에 갈 수 있는 정점들을 먼저 모두 처리하고, 그 다음..

문제 요약항목설명입력노드 수 N, 그리고 N-1개의 간선 정보중요간선은 부모→자식 방향이 아니라 그냥 연결 정보루트1번 노드를 루트로 고정출력2번 노드부터 N번 노드까지의 부모 노드 번호문제에서 주어지는 간선은 “누가 부모인지”를 알려주는 것이 아니라 “두 노드가 연결되어 있다”는 정보입니다. 그래서 반드시 1번에서 시작해 탐색하며 부모를 정해야 합니다.가장 많이 헷갈리는 부분헷갈림 포인트예제 입력에 1 6, 4 1 같은 줄이 섞여 있으니까 “그럼 1의 부모가 6인가?”, “왜 출력에서 부모가 1인 노드가 여러 개 나오지?” 하고 헷갈리기 쉽습니다.정답 해석1 6은 “1이 6의 부모다”가 아닙니다.그냥 1번 노드와 6번 노드가 연결되어 있다는 뜻입니다.부모 관계는 입력 순간에 정해지는 것이 아니라, 1을..

그리드, DP 로 풀수있지만 BFS로 풀어보기문제 요약항목설명입력동전 종류 수 n, 목표 금액 k, 그리고 각 동전 가치조건각 동전은 여러 번 사용할 수 있음목표합이 k가 되도록 할 때 사용한 동전 개수의 최솟값 구하기불가능하면-1 출력문제에서 요구하는 것은 단순히 만들 수 있는지 여부가 아니라, 최소 몇 개의 동전을 써야 하는지입니다. 이 코드를 왜 BFS로 볼 수 있을까?핵심 아이디어현재까지 만든 금액을 하나의 상태라고 보면 됩니다. 예를 들어 0원에서 시작해서, 동전 1개를 더하면 coins에 있는 금액들로 이동합니다. 다시 거기서 동전 1개를 더하면 다음 금액들로 이동합니다.상태 그래프로 보면0원 → 동전 1개 사용한 금액들 → 동전 2개 사용한 금액들 → 동전 3개 사용한 금액들...BFS는 1..

백준 실버 1 · BFS / 그래프 탐색문제 링크 : https://www.acmicpc.net/problem/2178문제 요약항목설명입력N, M 그리고 0과 1로 이루어진 미로이동 가능상, 하, 좌, 우 인접 칸의미1은 이동 가능, 0은 이동 불가목표(1,1)에서 (N,M)까지 가는 최소 칸 수 구하기왜 BFS를 써야 할까?핵심이 문제는 단순히 도착할 수 있는지만 보는 문제가 아니라, 최소 칸 수를 구하는 문제입니다. 이런 문제는 가중치가 없는 그래프의 최단거리 문제로 볼 수 있고, 가장 대표적인 풀이가 바로 BFS입니다.BFS가 맞는 이유BFS는 시작점에서 가까운 칸부터 차례대로 탐색합니다.즉, 어떤 칸에 처음 도착했을 때의 거리가 그 칸까지의 최단거리입니다.그래서 도착 지점에 처음 기록된 값이 곧 ..

이 문제는 DFS로 정점을 번갈아 색칠하면서 판별하는 대표적인 이분 그래프 문제다. 핵심은 인접한 두 정점은 반드시 서로 다른 색이어야 한다는 조건 하나다. [Source](https://www.acmicpc.net/problem/1707)문제 요약그래프의 정점들을 두 그룹으로 나누되, 같은 그룹 안의 정점끼리는 서로 인접하지 않게 분할할 수 있으면 그 그래프를 이분 그래프라고 한다. 입력으로 여러 그래프가 주어질 때, 각각이 이분 그래프인지 판별하면 된다. 항목내용입력테스트케이스 K, 정점 수 V, 간선 수 E, 그리고 E개의 간선 정보출력이분 그래프이면 YES, 아니면 NO핵심 판별 기준인접한 두 정점의 색이 항상 달라야 함이분 그래프를 쉽게 말하면정점들을 두 팀으로 나눌 수 있고, 같은 팀끼리는 간..

이 문제의 핵심은 “그래프 전체의 성질”을 보는 것이 아니라, 1번 컴퓨터에서 시작했을 때 실제로 도달 가능한 컴퓨터가 몇 대인가를 구하는 것이다. 즉, 1번과 연결된 컴포넌트의 크기를 구한 뒤 자기 자신을 빼면 된다. [Source](https://www.acmicpc.net/problem/2606)문제 요약웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 감염되면, 그 컴퓨터와 네트워크 상에서 연결된 모든 컴퓨터도 감염된다. 여기서 1번 컴퓨터가 감염되었을 때, 최종적으로 몇 대의 컴퓨터가 추가로 감염되는지를 구하면 된다.항목내용정점컴퓨터간선네트워크 연결 정보시작 노드1번 컴퓨터구해야 하는 값1번에서 출발해 도달 가능한 모든 컴퓨터 수 - 1문제를 한 줄로 바꾸면이 문제는 결국 “1번 노드와 연결..

이 문제는 코드보다 먼저 문제 상황을 정확히 해석하는 것이 더 중요하다. 현재 칸에 적힌 숫자만큼 오른쪽 또는 아래로 점프하면서, 오른쪽 아래 끝 칸에 도달할 수 있는지를 판단하는 문제다. [Source](https://www.acmicpc.net/problem/16173)문제 요약N × N 게임판이 주어지고, 시작 위치는 항상 왼쪽 위 칸이다. 현재 밟고 있는 칸의 숫자를 보고 그 수만큼 오른쪽 또는 아래로 이동할 수 있다. 마지막 칸에는 -1이 적혀 있고, 그곳에 도달하면 성공이다. 항목내용시작 위치(0, 0)이동 방향오른쪽, 아래만 가능이동 거리현재 칸 숫자만큼 정확히 이동목표오른쪽 아래 끝 칸(-1)에 도달 가능하면 HaruHaru, 아니면 Hing이 문제에서 제일 중요한 해석많은 사람이 처음에 ..

이 문제는 그래프를 직접 탐색해야 할 것처럼 보이지만, 실제 핵심은 훨씬 단순하다. 모든 국가를 여행할 수 있도록 하되, 비행기 종류 수를 최소로 만들어야 한다는 점만 정확히 이해하면 정답은 바로 나온다. [Source]문제 요약상근이는 N개의 국가를 여행하려고 하고, 주어진 비행 스케줄 안에서 가능한 한 적은 종류의 비행기를 타고 모든 국가를 방문하고 싶다. 한 국가에서 다른 국가로 갈 때 중간에 다른 국가를 거쳐 가도 된다. 항목내용입력테스트케이스 수 T, 각 테스트케이스마다 국가 수 N, 비행기 종류 수 M, 그리고 M개의 간선 정보출력모든 국가를 방문하기 위한 최소 비행기 종류 수핵심 해석모든 국가를 연결하기만 하면 되고, 최소 간선 수를 묻는 문제처음 보면 이렇게 접근하기 쉽다문제를 처음 읽으면..

이 문제는 복잡한 트리 알고리즘을 묻는 문제가 아니라, 리프 노드 개수를 정확히 맞추는 트리 구조를 직접 구성하는 문제다. 핵심은 “어떤 모양으로 연결하면 리프가 몇 개 생기는가”를 먼저 감각적으로 이해하는 것이다. 문제 요약항목내용입력정점 개수 n, 원하는 리프 노드 개수 m출력조건을 만족하는 트리의 간선 n-1개문제 핵심트리를 직접 “구성”해서 리프 개수를 맞추는 것중요 조건트리는 연결되어 있어야 하고, 사이클이 없어야 하며, 간선 수는 정확히 n-1개여야 함먼저 리프 노드부터 다시 확인하기리프 노드는 연결된 간선이 정확히 1개인 정점이다. 즉, 트리의 끝점이라고 생각하면 된다.예시: 일렬로 연결한 트리0 - 1 - 2 - 3이 경우 리프는 양 끝점인 0, 3 두 개다.이 문제의 핵심 아이디어이 문제..

위상 정렬은 방향 그래프에서 "무엇을 먼저 해야 하는가"를 정하는 대표 알고리즘입니다. 선수 과목, 작업 순서, 빌드 순서, 업무 의존성 같은 문제에서 자주 등장합니다.위상 정렬이란?위상 정렬은 방향 그래프에서, 간선의 방향을 거스르지 않도록 정점을 순서대로 나열하는 것입니다.쉽게 말하면 먼저 해야 하는 일을 먼저 배치하는 정렬입니다.예시 1. 선수 과목기초 과목을 먼저 듣고, 그 다음 중급 과목을 들어야 함예시 2. 작업 순서설계가 끝나야 구현을 시작할 수 있음예시 3. 빌드 순서라이브러리가 준비되어야 메인 프로젝트를 빌드 가능핵심 개념: 진입 차수(in-degree)진입 차수는 어떤 정점으로 들어오는 간선의 개수입니다.A → B이 경우 B는 A로부터 들어오는 간선 1개를 가지므로, B의 진입 차수는 ..