[백준] (골드4) 알파벳 [실패 코드 + 생각해볼 부분 + set을 쓰는 것이 왜 효율적인지]

BFS, DFS

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

1987번: 알파벳

 

실패 코드

import sys
from collections import deque
from string import ascii_uppercase

r, c = map(int, input().split())

board = [list(input()) for _ in range(r)]


def bfs(sx, sy):
	queue = deque([(sx, sy)])
	dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
	dic = {alpha : 0 for alpha in ascii_uppercase}
	dic[board[sx][sy]] = 1
	cnt = 1
	while queue:
		x, y = queue.popleft()
		for index in range(4):
			nx = dx[index][0] + x
			ny = dx[index][1] + y

			if 0<= nx < r and 0 <= ny < c:
				if dic[board[nx][ny]] == 0:
					dic[board[nx][ny]] = 1
					queue.append((nx, ny))
					cnt += 1

	print(cnt)

bfs(0, 0)

 

설명

 위 파이썬 코드는 예제 1, 예제 2 코드는 통과하는 코드가 된다. 하지만 예제 3 코드는 답이 4가 나와 통과하지 못하는 코드가 된다. 왜 그럴까? 위 BFS 코드의 흐름은 간략하게 설명해 보면 알파벳은 중복이 되면 안 되기 때문에 dictionary 자료구조를 활용하여 이미 방문한 알파벳은 1로 바꿔주고 그 외에는 0으로 초기화해주고 있다. 그럼 단순하게 생각해 보면 이런 생각이 든다. 그럼 알파벳을 최대한 많이 방문하게 되니까.. 최대한 많은 구간을 방문해서 찾지 않을까? 결론은 위 코드에 대해서는 절대로 최대한 많은 이동 경로를 확보할 수 없다. 그럼 왜 그럴까? 아래 구문을 읽고 좀 생각해 보면 아차 할 수 있을 것 같다.

 

 

dictionary로 관리해서 알파벳의 방문여부를 체크하는 게 과연 최대한 많은 이동경로를 확보할 수 있는가?

 

(문제설명)

"새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다."

 

 

 문제 설명부터 보자. 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과 달라야 한다고 나와 있다.

그러면 새로 이동한 칸이라는 말을 좀 생각해 볼 필요가 있다. 새로 이동할 수 있는 칸은 알파벳이 중복적으로 방문하지 않은 칸을 방문할 수 있는 칸으로 정의하고 있다. 다음은 dictionary자료구조를 생각해 보자. 중복적으로 방문하지 않기 위해서 알파벳을 1로 변경한다는 게 과연 이동경로가 최대가 될 수 있는가. BFS의 코드는 최단거리를 구할 때 보통 사용한다. 그렇기 때문에 방문한 곳은 방문하지 않게 된다. 이 문제에 적용하면 알파벳을 한번 방문하게 되면 다시 방문하지 않는다는 뜻이 된다. 그러므로 최소 이동거리가 구해진다는 것을 짐작해 볼 수 있다.

문제에서 구하고자 했던 것은 최소 이동거리가 아닌 최대 이동거리다. 따라서 위 코드는 절대로 최대한 많은 이동 경로를 확보할 수 없게 되는 것이다. 조금만 더 쉽게 풀어서 설명해 보면 한 지점으로부터 주변에 있는 정점들을 전부 방문한 뒤에 가장 먼저 큐에 삽입되었던 것이 그다음에 검사가 될 것이다. 하지만 이런 식으로 구현하게 되면 주변 정점들을 방문하게 됨으로써 모든 루트에 대해서 방문한 알파벳을 공유하게 된다.

 

그렇다면 문제 설명에 위배된다는 것을 알 수 있다. 왜냐하면 새로 이동한 칸에 적혀 있는 알파벳은 이전까지 나온 알파벳과 달라야 하기 때문이다. 하지만 알파벳을 공유하게 된다는 것은 독립적인 루트에 대해서 중복된 알파벳을 생각하지 않는다는 것이다. 최대로 이동하는 루트에 대해서는 그 역시 이전에 나온 알파벳은 존재하지 않을 것이다. 최대로 이동하는 루트가 아니더라도 뻗어 나가게 되는 모든 루트에 대해서 각기 다른 알파벳의 중복 여부를 검사하게 되면 공유하지 않기 때문에 방문을 더 이상 하지 못하는 문제를 해결할 수 있다.

 

 결국 알파벳이 중복되지 않아야 한다는 것에 집중한 나머지. 각기 다른 루트에 대해서 중복된 알파벳을 생각해야 된다는 문제를 바라보지 못했다.

 

 두 번째로 생각해 보아야 하는 부분은 메모리 초과에 대한 부분이다. 이 문제에서는 deque로 구현하게 되면 메모리가 초과되는 문제가 있었다. 왜냐하면 하나의 루트에서 시작해서 각기 다른 방향으로 가더라도 중복되는 경로가 생기기 때문이다. 이게 가능한 이유 역시 각기 다른 루트에 대해서 중복된 알파벳을 공유하기 때문이다. 그러므로 중복된 알파벳을 각기 다른 루트에 대해서 독립적으로 생각해서 도착한 그 지점은 다른 루트 또한 도착했다고 했을 때 같은 알파벳을 지나올 수 있는 가능성이 존재하기 때문이다. 그럼 왜 중복된 걸 제거해야 할까? 어차피 최대로 이동되는 루트는 구해지는 거 아닐까? 할 수 있지만 메모리 초과 부분에서 생각해야 하는 건 같은 루트에서 시작하더라도 같은 목적지에 도착한 부분이 같은 문자열이라고 했을 때 그 지점에서 4방향으로 가게 되는 부분은 역시 똑같고 4방 향다 갈 수 없다면, 다른 루트의 같은 루트를 지나온 부분 역시 아무 데도 갈 수 없다는 것을 의미한다. 따라서 1/2로 줄일 수 있기 때문에 중복 여부에 대해서 체크하게 된다면 단 하나의 루트만 검사하게 되면서 최대 루트인지 아닌지를 알 수 있게 되는 것이다.

 

 그럼 set자료구조를 쓰면 왜 효율적인가. 마찬가지로 중복된 경로에 대해서는 미리 제거가 되기 때문이다. 시작 지점은 같더라도 다른 경로에 도착했을 때 같은 문자열이라면 결국 같은 [r][c]에 도착한 것이기 때문에 그 부분에 대해서는 제거가 가능하다. 이게 set자료구조는 중복을 허락하지 않는다는 구조 덕분에 가능한 이야기가 된다.