프로그래머스 무인도 여행 C++

 

문제 설명

 

무지는 무인도로 여행을 가기 위해 지도를 보고있다.

지도에는 바다와 무인도에 대한 정보가 표시되어 있고, 지도는 1x1 크기의 사각형들로 이루어진 직사각형 격자 형태이다.

격자의 칸에는 바다를 나타내는 X 또는 1 ~ 9 사이의 해당 지역에 머물 수 있는 일수가 표시되어 있다.

상, 하, 좌, 우로 연결이 되어있는 지역은 하나의 무인도로 본다.

 

지도를 나타내는 문자열 배열 maps가 매개변수로 주어질 때, 맵에 있는 각 무인도에서 최대 며칠씩 머물 수 있는지

배열에 오름차순의 형태로 담아 return 하는 문제이다

만약 지낼 수 있는 무인도가 없다면 -1을 리턴한다.

 

문제 풀이

visited bool 방문 배열을 만들어서 해당 지역에 무엇이 있는지 확인하며 방문 처리를 한다.

이중 반복문을 통해 맵을 순회하며 시작지점을 정하고 상하좌우로 이동하고 방문처리를 한다.

숫자가 있다면 해당 방향을 더하고

없다면 여지껏 더한 값을 return 하여 준다.

bfs 사용

 

코드