[C++] 백준 2468번 안전 영역

2468번: 안전 영역

(문제가 길어서 캡쳐화면 대신 링크로 대체)

 

그래프 탐색 문제.

그래프 탐색에 브루트 포스(완전 탐색)를 곁들인(?) 문제이다.

문제를 이해하는 것도 어려웠고, 생각해야할 조건들도 까다로웠다.

 

문제풀이

일단 문제를 잘 해석해보면 연결 요소의 개수(ConnectedComponents)를 구하는 문제라는 것은 알 수 있다.

그리고 고려해야할 사항들이 있다.

• 물의 높이보다 낮거나 같으면 물에 잠긴다.
• 모든 도시가 물에 잠기지 않을 수도 있다. (연결 요소의 개수는 최소 0이 아니라 1이다.)
• 영역의 높이는 1 ~ 100까지이다. 그러나 최대 높이까지만 고려해주면 된다.

위에 조건은 당연하게 고려했어야 했는데 코드를 짜다보니 좀 꼬여서 고려하지 못했다.

DFS 메서드에서 고려해주고, 메인함수에서 DFS 진입시에도 고려해 주어야 한다.

 

코드를 살펴보자.

사용한 STL과 변수

memset 메서드로 배열을 초기화 하기 위해 cstring STL을 사용했다.

• widthHeight : n 높이를 나타내는 변수
• maxHeight : 각 영역의 높이 중 가장 높은 곳을 저장하는 변수. 저장해두고, 해당 높이까지만 브루트 포스 탐색을 한다.
• region : 각 영역의 높이를 저장하는 배열
• visit : 해당 영역을 방문했는지에 대해 저장하는 배열
• connectedComponents : 각 영역의 비의 높이를 0 ~ maxHeight - 1마다 구했을때 각각의 연결요소의 개수
• result : 결과, 최대 안전 영역의 개수

그리고 dfs 메서드는 상, 하, 좌 우로 탐색한다. 이 때, 그냥 리턴되는 경우가 있는데,

• y, x의 범위가 1보다 작거나 n의 크기보다 클 경우
• 해당 영역의 높이가 물의 높이보다 낮거나 같을 경우 -> 같을 경우를 고려하지 않아서 틀렸었다.
• 이미 해당 영역을 고려한 경우

 

메인함수

먼저 지역의 높이 widthHeight를 입력을 받는다.

그리고나서 지역에서 각 영역의 높이를 입력받는다.

지역에서의 최대 높이를 따로 변수에 저장해둬서 나중에 탐색을 할 때 줄여둔다.

 

그래프 탐색은 3중 for문으로 구성되어 있다.

• 가장 바깥쪽 for문 : 물의 높이를 나타내는 for문, 물의 높이 0(연결요소 개수 1)부터 최대 높이(연결 요소 개수 0이므로 고려하지 않음) 이전까지의 범위.
• 가운데 for문 : 지역에서의 Height
• 가장 안쪽 for문 : 지역에서의 Width

그리고 지역에서 해당 영역의 높이가 물의 높이보다 높고, 방문하지 않았다면 dfs를 시작한다.

그리고 그 정점을 시작으로 한 그래프(하나의 연결요소)가 방문처리가 되므로 연결요소를 1개 증가시킨다.

그리고 현재 기록된 result보다 connectedComponents가 크다면 result값을 업데이트 해준다.

 

물의 높이 하나를 돌 때마다, 연결요소의 개수를 0개로 초기화하고, 방문한 기록도 0으로 초기화 해준다.

 

처음에 문제를 틀려서, 왜 틀렸을까 하고 반례를 다 찾아봤는데도 틀렸다.

그러던 중, 물의 높이가 정수가 아닐수도 있다는 말을 듣고, 메인함수의 가장 바깥쪽 for문에서

0.1씩 증가시켜봤는데 문제를 맞긴 했지만, 시간이 너무 오래걸렸다.

다른 방법을 찾다가 DFS 메서드에서 위에 적어준 것처럼 고려하지 않은 사항이 있었다.(작거나 같으면 return)

해당 문제를 고치니 시간도 훨씬 줄어들고 문제도 맞을 수 있었다.

 

GitHub - kimyunseok/study-record: my study-record

코드 전문은 위에서 확인 가능하다.