목록전체 글 (17)
주니어 개발자의 대나무숲
1. 개념 BFS(Breadth First Search)는 그래프 전체를 탐색하는 방법 중의 하나입니다. 그래프 전체를 탐색하는 방법은 크게 BFS와 DFS, 두 가지가 있다고 할 수 있습니다. 그 둘 중 오늘은 BFS에 대해 배워보도록 하겠습니다. BFS의 핵심은 그래프 전체를 탐색하되, 인접한 노드들을 차례대로 방문하도록 구현한다는 점입니다. 그리고, 이를 구현하기 위해 STL의 queue를 사용하게 됩니다. 인접한 노드들을 먼저 방문한다는 말이 잘 이해가 안되신다면, 아래의 그림을 통해 이해하실 수 있을 겁니다. 위의 그림은, 노드 A부터 시작해서 BFS로 모든 노드를 방문하는 것을 나타낸 모습입니다. BFS는 인접한 노드들을 차례대로 방문한다고 했었습니다. 시작 노드인 노드 A에 인접한 노드는 노..
그래프 관련 문제를 풀 때는, 문제 상황을 그래프로 모델링한 후에 푸는 것이 보편적입니다. 이 때, 모델링한 그래프의 연결관계를 나타내는 두 가지 방식이 있습니다. 1. 인접 행렬2. 인접 리스트 1. 인접 행렬 1) 정의인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식입니다. 인접 행렬을 adj[][]라고 한다면 adj[i][j]에 대해서 다음과 같이 정의할 수 있습니다. adj[i][j] : 노드 i에서 노드 j로 가는 간선이 있으면 1, 아니면 0 cf) 만약 간선에 가중치가 있는 그래프라면 1 대신에 가중치의 값을 직접 넣어주는 방식으로 구현할 수 있습니다. 2) 예시간단한 예시를 통해 이해해보도록 하겠습니다. 다음과 같은 그래프가 있는 경우, 이 그래프의 연결 관계를 인접 행렬로 나..
BOJ 13417 카드 문자열 (https://www.acmicpc.net/problem/13417) 이 문제는 한 면에 문자가 써 있는 카드를 왼쪽부터 하나씩 가져와 재배열하는데, 재배열한 카드들의 왼쪽 끝과 오른쪽 끝에만 카드를 놓을 수 있는 경우 사전순으로 가장 빠른 문자열이 되도록 재배열하는 문제입니다. 이 문제는 각각의 카드를 재배열할 때, 왼쪽 끝에 놓을 것인지 오른쪽 끝에 놓을 것인지를 판가름하는 기준이 무엇일지만 알면 쉽게 풀 수 있습니다. 예제로 나와있는 M,K,U에 대해 생각해 보겠습니다.M은 첫 번째 카드이므로 그냥 올려놓은 후, K를 추가할 때의 상황입니다. K를 M의 왼쪽에 올려놓아야 할까요 아니면 오른쪽에 올려놓아야 할까요? 답은 왼쪽입니다. 이유는 왼쪽에 올려놓는 경우와 오른쪽..