[백준 / #1987 / C++] 알파벳

이번 문제는 아주아주 쉽게 풀리는 문제였다.

 

 

https://www.acmicpc.net/problem/1987

1987번: 알파벳

 

참고로 필자는 문제를 풀기 전에 이 문제가 어떤 알고리즘 분류인지 힌트를 보지 않고 풀기 시작한다. 문제를 처음 봤을 때

 

어떤 알고리즘을 사용해야 하는지 판단하는 훈련도 같이 하기 위함이다. 문제를 푸는 기준은 그냥 solved.ac에 들어가서 티

 

어에서 많이 푼 순서대로 풀어나가고 있다. 잡설은 여기까지 하고 문제를 살펴보자.

 

 

 

문제해석:

 

 

문제에서 주어진 R과 C는 각각 좌표계의 관점에서 보면 Y축과 X축에 해당한다. R과 C는 최소 1, 최대 20 이하로 이루어져

 

있어서 자료의 크기가 그렇게 큰 편은 아니다. 하지만 문제에서 원하는 바는 알파벳 중 중복이 되지 않게 방문하면서 최대

 

로 방문할 수 있는 칸 수이다. 최대로 방문할 수 있는 칸의 수를 구하려면 가능한 모든 경우의 수를 방문해보고 최대 크기를

 

구해주면 되는데 이는 전에 문제들과 굉장히 흡사하며 바로 깊이우선탐색(DFS)를 사용하여 풀면 되는 것을 눈치 챌 수 있

 

을 것이다. 처음에는 백트래킹을 생각하며 문제를 풀었는데 코드를 짜고 보니 결국에는 모든 경우의 수를 찾아 비교해준다

 

는 점이 DFS에 더 가까운 것 같아서 DFS라고 했다. 거두절미하고 코드를 보면서 설명하겠다.

 

 

알고리즘 해설 및 코드:

 

 

이 문제의 핵심이 되는 부분은 알파벳의 중복체크를 어떻게 해주냐인 것 같다. 아무래도 DFS의 기본 진행 방식은 크게 다

 

른 점이 없어서 중복체크만 잘 해주고 상하좌우의 이동에 있어서 가능한지 여부를 파악해주는 것이 중요하다. 우선 상하좌

 

우의 이동에 있어 코드를 조금 더 간결하게 보여주기 위해 행과 열의 이동 칸 수를 배열에 넣어주고 차례대로 왼쪽, 위, 오

 

른쪽, 아래 순으로 방문하게끔 해주었다. 이렇게 돌아가면서 방문하면서 배열의 범위에 벗어나지 않게 범위 설정을 해주고

 

만일 이미 방문했던 알파벳이면 재귀호출의 끝에 도달해 기존에 저장되어있던 칸 방문 수와 비교하고 갱신이 필요하다면

 

해주고 그 전의 연산으로 돌아가는 형식이다. 또한 이렇게 재귀를 호출하면서 이미 지나온 칸의 중복 방문을 막기 위해 칸

 

을 지워줬지만 이러한 연산은 필요가 없다는 것을 알아둘 필요가 있다.(글을 쓰면서 깨달은 사실이다.) 그 이유는 이미 알파

 

벳을 방문처리를 해줬기 때문에 굳이 연산을 추가할 필요가 없는 것이다. 그럼 이제 알파벳 방문 처리를 어떻게 할 것인가

 

이다.

 

 

아스키코드 표를 가져오지는 못했지만 별도로 검색해서 지금 틀어보길 바란다. 아스키 코드표를 보면 대문자 'A'를 10진법

 

수로 나타내면 65이다. 또한 그 뒤로 차례대로 알파벳들이 나열된다.(66, 67, 68...) 이는 곧 char형식으로 입력받은 알파벳

 

에서 int 형식에 넣어 'A'를 빼주면 그 값은 0, 1, 2..로 배열의 인덱스로 활용하기 너무나도 좋은 값이 된다. 따라서 bool 타입

 

의 alphabet 배열을 하나 만들어 이렇게 빼준 값의 인덱스에 해당하는 알파벳의 방문 여부를 체크해준다. 그렇게하면 방문

 

여부를 그냥 DFS의 중간에 체크만 해주면 된다. 이러한 프로세스를 거쳐 코드를 완성하였다.

 

 

 

 

 

이 문제는 깊이우선탐색(DFS)사용 여부와 아스키코드를 활용할 생각만 했다면 매우매우매우 금방 풀 수 있을 것이다.