DMLab 알고리즘 스터디 12주차

개요

12주차 스터디는 DFS 관련 문제들을 풀었다.

A번

2644

문제 요약

부모자식 관계들이 주어졌을 때, 두 사람의 촌수를 출력하는 문제다.

설명

그냥 DFS로 풀 수 있다.

B번

17472

문제 요약

복잡해서 생략. 직접 눌러서 보자.

설명

1. DFS로 섬들마다 ID들을 만들어준다.
2. 섬의 개수를 N이라 하면, N*N으로 섬들을 연결하는 간선들을 만들어준다.
3. MST를 만든다. 나는 크루스칼(UF)를 썼다.

굉장히 귀찮았다.

C번

11123

문제 요약

위 문제에서 섬의 개수를 출력하는 것이랑 같다고 생각하면 된다.

설명

그냥 DFS로 풀 수 있다.

D번

17265

문제 요약

그리드에 수와 사칙연산이 적혀있을 때 오른쪽과 아래로 이동이 가능하다.
가장 오른쪽 아래로 갔을 떄 최대값과 최소값을 출력하는 문제다.

설명

N이 너무 작아서 아마도 BF로도 풀릴 것이다. (아마 BF로 BFS를 하는 게 정해인 것 같다.)
나는 DP로 풀었다.

후기

ICPC가 끝나고 본격적인 PS는 잠시 휴식중인데, 오랜만에 간단한 문제들을 푸는것도 나름 재미있었다.