[C++] 백준 10026번 적록색약

그래프 탐색 문제.

그래프 탐색 문제는 문제를 잘 이해하고 코드로 잘 구현하면 어렵지 않게 맞출 수 있다.

골드 문제지만, 쉽게 맞출 수 있는 문제였다.

DFS로 풀면 최악의 경우 100 * 100번 탐색하므로 10,000번 이므로 시간 내에 완벽하게 풀 수 있다.

 

문제풀이

어려운 문제는 아니다. 그냥 연결요소의 개수를 구하는 문제인데,

적록색약이 빨간색과 초록색을 같은 색으로 보는 것을 유의하면서 문제해결을 해주면 된다.

 

사용한 STL과 변수

memset() 메서드를 사용해서 초기화 하기위해 cstring STL을 사용했다.

• widthHeight : 입력받는 길이 n
• board 배열 : 입력받는 그리드를 저장하는 char 배열이다.
• visit 배열 : DFS를 할 때 이미 방문한 곳인지 체크하는 배열이다.
• normalResult, redGreenSameResult : 일반인의 연결요소의 개수와 적록색약의 연결요소의 개수이다.

일반인의 연결요소를 구하기위한 DFS

일반인의 경우, 따로 고려해줄 건 없고 내가 맨 처음 탐사하기 시작한 곳과 같은 색깔의 영역만 탐색하도록 DFS를 설계해주면 된다.

적록색약을 구하기 위한 DFS

적록색약의 경우, 만일 처음 탐사하기 시작한곳과 같은색깔의 영역만 탐색하도록 하되, 다른 색깔이 나올 경우에 초록색과 빨간색의 경우라면 탐사를 계속하도록 설계해주면 된다.

 

메인함수 - 1

맨 처음 길이 n을 입력받고 각 칸의 어떤 색이 칠해져 있는지 입력받는다.

메인함수 - 2

그러고나서 일반인DFS와 적록색약DFS를 하되, 적록색약 DFS 시작전에 visit배열을 초기화해준다.

그리고 구한 각각의 연결요소의 개수를 출력해준다.

 

그래프 탐색은 쉽게 맞췄다.

이제 골드 문제도 슬슬 많이 풀어봐야겠다.

 

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

코드는 위에서 확인 가능하다.