코딩테스트 기록 7일차

코딩테스트 기록 7일차

1. 24479번: 알고리즘 수업 (메모리: 87884KB, 시간: 1008ms)

Problem Link
Solved Link

문제 정리

• 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000),시작 정점 R (1 ≤ R ≤ N)이 주어진다가 주어진다.
• N개의 정점과 M개의 간선으로 구성된 무방향 그래프에서, 정점 R에서 시작하는 깊이 우선 탐색(DFS)을 수행하여 각 정점의 방문 순서를 출력한다.
• 모든 간선의 가중치는 1이며, 방문할 수 없는 정점의 방문 순서는 0으로 출력한다.

개념 및 접근법

• 깊이 우선 탐색(DFS) 알고리즘을 사용하여 각 정점을 방문한다.
• 인접 정점은 오름차순으로 방문한다.
• 방문 순서를 기록하기 위한 배열을 사용한다.
• 시작 정점에서 탐색을 시작하여 모든 연결된 정점을 방문하고, 방문 순서를 기록한다.

2. 24444번: 알고리즘 수업 - 너비 우선 탐색 1 (메모리: 99920KB, 시간: 1844ms)

Problem Link
Solved Link

문제 정리

• 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000),시작 정점 R (1 ≤ R ≤ N)이 주어진다.
• 주어진 입력은 N개의 정점과 M개의 간선으로 구성된 무방향 그래프입니다.
• 모든 간선의 가중치는 1입니다.
• 정점 R에서 시작하여 너비 우선 탐색(BFS)을 통해 각 정점의 방문 순서를 출력해야 합니다.

개념 및 접근법

• BFS를 이용한다.(Queue사용)
• 인접한 정점(edge값)을 오름차순으로 방문하기 위해, 해당 인접 리스트를 정렬.

3. 10026번: 적록색약 (메모리: 16492KB, 시간: 176ms)

Problem Link
Solved Link

문제 정리

• N*N 크기의 그리드의 각 칸에 R,G,B값만 채워지는 그림이 있다.
• 같은 색상이 상하좌우로 인접해 있으면 같은 구역으로 취급한다.
• 적록색약인 사람은 G,R을 구분하지못해서, 같은 색상으로 취급한다.
• 적록색약인 사람과, 아닌 사람이 볼 때의 구역 수를 각각 구하라.

개념 및 접근법

• BFS를 사용해 각 구역의 인접 칸을 탐색하며 구역의 수를 구한다.
• 적록색약은 R을 G로 바꾸거나, G를 R로 바꾸어 동일한 색상으로 처리하게 한다.

4. 7562번: 나이트의 이동 (메모리: 106928KB, 시간: 392ms)

Problem Link
Solved Link

문제 정리

• 나이트가 원하는 칸에 이동할 수 있는 최소 거리를 구하라.

개념 및 접근법

• 최소 거리 문제이기에 BFS를 사용한다.
• 체스판의 위치를 그래프의 노드, 이동을 간선(edge)로 생각한다.
• BFS 알고리즘은 시작 노드에서 가장 가까운 노드부터 방문하기떄문에, 목표 노드에 도달한다면, 그 시점의 이동 횟수가 최소 이동횟수가 된다.