❗문제 메모 - 그래프❗

해결한 문제의 양이 증가하면서 좋은 문제를 양치기만 하고 끝내면 안 될 것 같다는 생각이 들었다.

이 게시물에 푼 문제들에 대한 간단한 기록을 남겨보고자 한다.

 

## 노란색 복습 필요 x

## 초록색 복습 필요 o

## 빨간색 복습 진행 했으나 아직도 어려움

## 보라색 개중요

## 회색 잘 풀었는데 다시 보면 좋을 듯?

 

깊이 우선 탐색 / 넓이 우선 탐색

 

백준 2468번 안전영역 (실버1) / 2667번 단지번호 붙이기(실버1)

 

문제를 풀며 단지번호 붙이기와 유사하네? 라는 생각이 들었다. 우선 안전영역 문제는 비가 점점 차오른다고 가정했을 때, 각자 떨어져 있는 안전영역의 개수를 세고 -> 비가 점점 차오르던 각각 시기의 안전영역 개수 중 가장 큰 값을 return 하는 문제이다. 

단지번호 붙이기는 떨어져있는 각 단지의 아파트 개수를 출력하는 것이고, 안전영역은 rain이 증가할 때마다 바뀌는 안전영역의 개수를 출력해야 한다는 차이점이 존재한다. 그러나 2차원 리스트 전체를 돌면서 방문하지 않은 장소를 찾아낸다는 점에서 유사했기 때문에 금방 해결할 수 있었다.

 

백준 2573번 빙산 (골드4)

 

빙산과 인접해 있는 바다의 칸 수 만큼 빙산이 녹는다. 이 때, 빙산의 덩어리가 2개 이상으로 분리되는 최초의 시간을 출력해주는 문제다. 문제 자체는 위의 안전영역 문제와 유사한데, 조건이 많아서 조금 까다로웠다.

인접한 바다의 칸 수를 한 번에 빼줘야 하는 것과 빙산 덩어리의 개수를 확인해주고 빙산이 녹는 것을 후처리 해줘야 하는 등 삐끗하면 논리적으로는 맞는데 왜 틀림? 이런 생각이 들 수도 있을 문제였다.

 

최단경로 - 다익스트라 / 플로이드워셜 / 벨만포드

 

다익스트라

 

백준 13549번 숨바꼭질3 (골드5) => deque 사용해서 bfs로 풀어보기 ✨

 

수빈이가 동생의 위치에 도달하기 위해 걸린 시간 중 최솟값을 출력하는 문제다. 숨바꼭질1,2 문제와 다른 점은 순간이동을 하면 시간이 증가되지 않는다는 점이다. 다익스트라로 잘 푼 줄 알았는데, 수빈이가 동생보다 큰 위치에 있을 경우를 생각하지 못해서 계속 틀렸었다. 당연히 동생의 위치가 더 클 거라고 생각해서 k*2 이상 넘어가면 continue 하게 했었는데, 반대의 경우가 있었다. 그래서 범위 제한을 0 <= i <= 100001 으로 걸어서 해결했다.

0과 1 두 개의 가중치만 있을 경우 deque로 우선순위를 달리 해서 풀면 된다는데 이건 오늘의 공부 범위에 벗어나서 나중에 다시 해결하러 와야겠다.

 

백준 1238번 파티 (골드3)

 

n개의 마을에 각각 살고있는 학생이 파티를 끝내고 집으로 돌아가며, 이 때 왕복 거리가 최대인 학생을 출력한 문제다. 전에 풀었던 특정한 최단경로(1504번, 반드시 하나의 경로를 거쳐야 하는 것)와 유사한 문제라서 크게 어렵진 않았다.

(각 학생이 사는 위치 -> 파티 개최지) + (파티 개최지 -> 각 학생의 사는 곳) 즉 n * 2번의 다익스트라 알고리즘을 실행시키면 간단하게 해결할 수 있다.

 

플로이드워셜

 

백준 1956번 운동 (골드4)

 

cycle이 도는 지점 중 가장 최솟값을 확인하는 문제다. 평소 알고리즘을 작성할 때는 cycle을 고려하지 않기 때문에 i == j인 곳(출발 지점과 도착 지점이 같은 곳)은 0으로 잡고 시작한다. 그러나 이 문제에서는 이 부분을 지우고, dist[i][i] 즉, i에서 출발해서 다른 곳을 거쳐서 i로 도착한 부분의 값을 찾으면 된다.

 

백준 14938번 서강그라운드 (골드4)

 

모든 정점에서 수색 범위 내에 있는 정점을 방문할 것이다. 방문 가능한 정점에 있는 item 수를 변수에 더해주고, 각 정점의 변수가 가지고 있는 값 중 최댓값을 출력하면 되는 문제다. 플로이드와 다익스트라 모두 해결 가능하고, 플로이드를 잘 알고 있다는 전제 하에 조건만 맞게 잘 풀면돼서 쉽게 해결할 수 있었다.

 

벨만포드

 

백준 1865번 웜홀 (골드3)

 

시작점을 정하지 않고, 나라 어딘가에 존재하는 음수사이클의 여부를 찾는 문제다. dist[v] != INF 의 의미를 정확히 몰라 많은 시간이 걸렸다. dist[v] != INF 는 단절되어 있는 경우를 뜻한다. 따라서 이 조건을 없애면 dist의 값이 INF여도 단절된 것이 아닌 이어져 있다고 인식이 되고, 음의 사이클을 찾을 수 있다.

+ 그러나 단절되어 있는 정점을 인식할 수 없다는 단점이 존재한다. 따라서 N+1이라는 가상의 정점이 모든 정점과 이어져있다고 가정하고 벨만포드를 다시 돌리면 올바른 정답을 도출할 수 있다.

 

그 외 Graph

 

UNION FIND

 

백준 1976번 여행 가자 (골드4)

 

한국에 있는 도시의 연결 여부가 주어지고, 여행 계획에 속한 도시가 순서대로 주어졌을 때 그것이 가능한지 판별하는 문제다. 다른 도시를 경유해서 가도 되고, 같은 도시를 여러번 방문하는 것도 가능하며, 무방향 그래프인 문제기 때문에 union find를 이용하면 된다. 각 도시가 연결되어 있으면 union 연산을 돌린 후 find 연산을 통해 여행 계획에 속해 있는 곳의 root node가 모두 같은지 확인하면 된다.

 

백준 1717번 집합의 표현 (골드5)

 

주어진 원소가 집합에 포함되어 있는지 확인하는 문제인 전형적 union find 문제다. 재귀로 문제를 풀 때(특히 union find랑 dfs) sys.setrecursionlimit(100000) 작성해주는 것 잊지 말자.

 

 

 

 

 

DFS/BFS

- 백준 2206번 벽 부수고 이동하기

- 백준 13023번 ABCDE