sw expert academy 7699번 수지의 수지 맞는 여행 자바(java) 풀이
문제정리
- 섬은 R행 C열로 이루어져있다.
- 알파벳은 섬의 명물이고 같은 알파벳을 가지면 같은 명물을 가진다.
- 수지는 1행 1열에서 여행을 시작한다.
- 명물을 볼때 마다 요금을 지급하며, 처음 볼때는 무료이다.
- 명물을 본 후 4방향(상,하,좌,우)중 한 방향으로 이동 가능하다.
- 같은 알파벳 명물을 두 번 이상 보지 않도록 여행을 떠나는 방법 중, 볼 수 있는 최대 명물의 개수를 구해라
문제플이
이 문제와 디저트 카페 문제가 유사합니다. 같이 풀어보시는걸 추천드립니다!!
- 출발점이 정해져있으므로 map의 (0,0) 위치에서 dfs를 통해 탐색하면 됩니다.
- dfs를 돌기전 출발점 방문체크, 출발점 알파벳을 방문 체크합니다.
- 4방향을 모두 따져서 방문할 수 있는 곳만 방문하며 조건은 다음과 같습니다.
map을 넘는 위치가 아니어야 합니다.
방문하지 않은 곳이어야 합니다.
방문하지 않은 알파벳이어야 합니다.
- 방문을 하면 그 점(dx, dy)과 k(방문한 섬의 수)를 1 증가시켜 넘겨줍니다.
- 4방향 모두 방문 하였다면 함수 끝에서 max와 k를 비교하여 max값을 update 시켜줍니다.
방문한 알파벳 체크
이와 같은 방식은 자주 쓰이기에 기억해두시면 좋습니다!!
이를 체크하기 위해서 1차원 boolean 배열을 이용합니다. 배열음 다음과 같은 값을 나타냅니다.
만약 aVisited[0]이 true라면 A라는 명물을 본 것입니다. aVisited[25]=true라면 Z 명물을 본 것입니다.
알파벳을 숫자로 바꾸기 위해서 아스키 코드 값을 이용합니다.
'A' - 'A' : 0
'B' - 'A' : 1
'C' - 'A' : 2
...
'Z' - 'A' : 25
문자 A와 문자 B는 아스키 코드 값으로 1차이가 납니다. C와는 2차이..Z와는 25차이가 납니다.
그렇기 때문에 문자 'A'를 빼면 숫자 값으로 바꿀 수 있습니다.
이를 이용하여 다음과 같이 같은 알파벳을 봤음을 체크할 수 있습니다.
aVisited[map[dx][dy] - 'A'] = true; // map[dx][dy] 알파벳 방문 체크
aVisited[map[dx][dy] - 'A'] = false // map[dx][dy] 알파벳 방문 해제
수지의 수지 맞는 여행 자바코드