[BOJ 백준] 1987 - 알파벳

 

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

1987번: 알파벳

백트래킹을 연습하기 위해 약 1달전, 2월 4일에 풀었을 때 틀렸던 문제를 다시 풀어보았다. 

 

그때 트렐로에 남겨둔 메시지는 이랬었다.

 

 

두가지 코드 모두 dfs의 기본적인 개념을 모르고 있어서 저러한 메시지를 남겼었고, 다른 사람의 코드를 봐도 이해하지 못했던 것이다.

 

한 달이 지난 지금, 다시 풀었을때 걸린시간은 딴 짓 포함 40분이었다. 그래도 이제는 백트래킹의 기본적인 문제를 풀 수 있게 된 것 같다. 물론 소스코드는 조금 비효율적으로 구현하였다.

 

 

사용된 변수, 함수는 다음과 같다

 

• 입력을 받는 map[][]
• 방문했던 알파벳인지를 확인해주기 한 alpha[]
• 해당 위치를 방문했음을 체크하는 visit[][]  --> 사실 이건 필요 없다. alpha로 충분히 체크 가능하다.
• 4방향 탐색을 위한 dy[] , dx[[]
• 백트래킹을 하기위한 dfs() 
  • dfs 함수의 파라미터에는 (y좌표, x좌표, 지나온 칸의 개수) 가 들어간다.
• 4방향 모두 전진을 하지 못하는 상황을 나타내는 flag 변수인 is_move 변수

 

구현한 로직은 다음과 같다

 

• 첫 칸도 지나온 칸에 포함해야하므로 dfs 시작전에 방문체크를 해준다.
• dfs 함수 내부에서 depth값과 result 값을 비교하여 최대값을 result 에 저장한다.
• 4방향 탐색을 하고 방문하지 않은 지점에서 depth 값을 1증가시켜 dfs 함수를 재귀호출한다.

 

굳이 visit 배열을 사용하지 않아도, alpha 배열 하나만으로 방문확인이 가능한데 중복으로 만들었다. 

탈출조건도 굳이 없어도 되는건데 is_move 라는 변수를 사용하여서 탈출할 수 있도록 하였다. 

 

 

 

소스코드

 

 

 

좀 더 깔끔한 소스코드