[BOJ] 알파벳_1987

 

이 문제는 풀지 못하였다.

 

해설을 보고 어떻게 푸는지를 보았고, 내가 모르는 부분들에 대해 정리해야겠다.

 

몰랐던 부분

1. 람다식을 통한 배열 만들기

graph = [list(map(lambda x: ord(x)-65, input())) for _ in range(n)]

input()으로 입력 받은 값을 람다와 딕셔너리를 이용해서 숫자로 바꾼 리스트 값을 n 만큼 추가하였다.

지금 다시 봐도 생소한 느낌이다. 앞으로 파이썬 배열을 초기화할 때, 컴프리헨션으로 만들자.

 

 

2. 재귀함수를 이용한 풀이법.

 

이 문제는 각 경우에 마다 쭈우욱 가본 결과의 경우들을 모아서 그 중에 최대의 결과를 구하는 문제이다.

그랬을 경우, 백트래킹과 같은 방식을 사용하여 모든 경우를 파악해야했다.

 

그렇다면 문제를 풀 때 재귀함수는 어떻게 활용이 될까?

예를들어, 재귀함수에서 dfs()코드 안에 dfs()코드가 있는 것을 재귀라고 하겠다.

재귀 앞에 잇는 코드는 한 경우에 대해 실행하는 코드이다.

재귀함수를 통해 어떠한 경우에 대해 계속 들어가는 과정에서 실행되는 것은 재귀함수의 앞 부분이기 때문이다.

 

나는 재귀함수를 저 네모칸처럼 이해했다. 끝까지 파고 들어간 것부터 실행되고, 그 이후에 재귀함수 뒤에 있는 것이 실행되기 때문이다.

그림과 같은 코드는 재귀함수 앞쪽에 코드들을 실행하며 쭈욱 판다. 

처음에 이 코드를 보고 헷갈렸던 부분은 4가지 방향에 대해 고려해주지 않은 것 아닌가 헷갈렸다.

상하좌우를 순서로 했을 때, 상부터 본다면 그 다음 하 방향에 대해 영향을 주지 않을까 하는 생각을 했다.

하지만 재귀함수는 한가지에 대해 우선 파보는 것이기 때문에 다음 방향에 대해서는 재귀 뒤쪽 코드가 실행된 후 이기 때문에 영향을 주지 않게 할 수 있다.

 

이것이 백트래킹이라고 하나보다.

쭈우욱 가다가 뒤로 빠지고 다시 가서.

 

bfs는 문제에서 모든 경우를 전체적으로 처리해줘야할 때 쓰이고,

dfs는 한 경우에 대해 쭈우욱 간 다음 그러한 경우를 모두 고려한 결과물들에서 어떤 한가지 경우를 고를 때 사용하는 것 같다.