문제 풀이/백준 (BOJ)

[백준/BOJ] 1707번: 이분 그래프 ( 깊이 우선 탐색, DFS 활용법 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/1707 풀이이 문제는 주어진 그래프가 이진 그래프( Bipartite Graph )인지 판단하는 문제입니다. 이진 그래프는 그래프의 모든 정점을 두 그룹으로 나눌 수 있는 그래프를 말합니다.예를 들어, 한 정점이 그룹 1에 속하면, 그와 인접한 모든 정점은 그룹 2에 속해야 합니다. 만약, 모든 정점을 두 그룹으로 나눌 수 있다면, 모든 정점을 인접한 정점과 다른 색상으로 칠할 수 있다는 얘기가 됩니다. 이와 비슷한 문제로 4색 문제가 있습니다.4색 문제는 평면을 유한 개의 부분으로 나누어 각 부분에 색을 칠할 때, 서로 맞닿은 부분을 다른 색으로 칠한다면 네 가지 색으로 충분하다는 정리입니다. 이 문제 풀이는 깊이 우선 ..

2024. 6. 21.

문제 풀이/백준 (BOJ)

[백준/BOJ] 2667번: 단지 번호 붙이기 ( 깊이 우선 탐색, DFS 활용법 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/2667 풀이이 문제에서 연속되는 숫자 1들의 집합을 단지라고 합니다.이 단지들의 숫자를 출력하고, 각 단지에 속한 숫자 1의 개수를 오름차순으로 출력하는 문제입니다. 먼저 입력을 받아봅시다.#define SIZE 25bool exist[SIZE][SIZE];int N = 0;cin >> N; // 지도의 크기string str;for( int i = 0; i > str; for( int j = 0; j 정사각형의 지도에 들어있는 0과 1을 N*N 배열에 입력하는 코드입니다. 그다음엔, 숫자 1을 만나면 그 1과 연결되어 있는 1들을 찾는 과정입니다.이때, 숫자 1과 인접한 1들을 탐색하는 방법으로 깊이 우선 탐색법을 ..

2024. 6. 17.

문제 풀이/백준 (BOJ)

[백준/BOJ] 2606번: 바이러스 ( 깊이 우선 탐색, DFS 활용법 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/2606 풀이이 문제는 1번 컴퓨터에서 시작하여, 도달할 수 있는 컴퓨터의 숫자를 알아내는 문제입니다. 컴퓨터의 번호를 정점(vertex)으로 하고, 컴퓨터 간의 연결을 간선(edge)으로 보면, 컴퓨터 네트워크를 일종의 그래프로 볼 수 있습니다.그러면, 이 문제는 입력된 그래프에서 1번 정점부터 시작하여 도달할 수 있는 정점의 개수를 구하는 문제로 생각할 수 있습니다. 그래프의 정점들을 탐색하는 방법은 크게 깊이 우선 탐색과 너비 우선 탐색법으로 나눌 수 있습니다.여기에선 깊이 우선 탐색(DFS)을 사용했습니다. 깊이 우선 탐색에 관한 자세한 내용은 여기에 있습니다. [백준/BOJ] 24480번: 깊이 우선 탐색 2 ( D..

2024. 6. 17.

문제 풀이/백준 (BOJ)

[백준/BOJ] 24480번: 깊이 우선 탐색 2 ( DFS, Depth-First Search ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/24480 풀이이 문제는 각 정점을 방문하는 순서를 출력하는 문제입니다.정점을 방문하는 방식은 깊이 우선 탐색( Depth-first Search, DFS )을 따릅니다. 깊이 우선 탐색은 이웃하는 노드가 아니라 자식 노드를 먼저 탐색하는 방식입니다.이미지를 보면서 설명을 읽는 것이 쉽게 이해할 수 있을 것 같습니다.  위의 이미지에서 탐색 경로는 다음과 같습니다.먼저 루트(root)인 1부터 탐색을 시작해서, 자식 노드인 2를 탐색합니다.그다음은 이웃 노드인 3이 아니라, 2의 자식 노드인 3을 탐색하고, 차례로 자식 노드인 4, 8까지 "자신 노드 우선"으로 탐색을 합니다.그리고, 그다음은 8 노드에서 한 단계 올라가, ..

2024. 6. 13.