1987.md

백준 1987번 알파벳

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

---

코드 설명

• 알고리즘 자체는 아래 오답코드와 같다. 단지 차이가 있다면 set에 tuple형식으로 좌표와 알파벳문자열을 넣었다.
• 문자열을 통해 지나쳐온 알파벳인지 아닌지를 확인했으며, 새로운 알파벳이라면 문자열에 + 해주는 식으로 알파벳을 추가해줬다.
• 최대 길이는 문자열의 길이를 통해 max 해 구했으며, 확실히 bfs가 dfs보다 빠르다는 것을 알 수 있었다.
• dfs로 풀고 싶어 시간을 최대한 단축하고자 set를 이용했지만 재귀자체가 오래 걸리는 것같아 시간초과를 피할 수 없었다.

소스코드

• 메모리 : 49292 KB
• 시간 : 1948 ms

import sys

def bfs():
	ans = 1
	sets = set()
	sets.add((0,0,matrix[0][0]))

	while sets: 
		x, y, alpha = sets.pop()
		for dx, dy in zip(dxs, dys):
			nx, ny = x + dx, y + dy
			if 0 <= nx < r and 0 <= ny < c and matrix[nx][ny] not in alpha:
				new = alpha + matrix[nx][ny]
				sets.add((nx,ny,new))
				ans = max(ans,len(new))

	return ans

r, c= tuple(map(int, input().split()))
matrix = [list(sys.stdin.readline().strip()) for _ in range(r)]

dxs, dys = [1,-1,0,0], [0,0,1,-1]

print(bfs())

오답 노트

• 처음에는 dfs로 풀려고 시도했었다. -> 시간초과
• 알파벳을 set에 저장한 뒤 dfs 함수내에서 상하좌우 확인하면서 알파벳이 set에 있으면 다른 방향을 탐색하고, 없으면 set에 넣어준 뒤 그 방향쪽으로 dfs 이동하도록 했다.
• 만약 상하좌우를 다 확인했는데 모두 이미 set 안에 있는 알파벳이라면, 다시 왔던 길로 돌아가도록 했다. -> 이때 remove를 통해 back한 알파벳은 삭제했다.
• 이 문제자체가 파이썬으로 풀기에는 무척 힘들었다. 특히 dfs로 풀면 시간초과가 나기 일수 였다. 따라서 bfs로 수정해 풀었다.

오답 코드

import sys

def in_range(x,y):
	return x >= 0 and x < r and y >= 0 and y < c

def dfs(x,y,cnt):
	global answer
	
	answer = max(answer,cnt)
	for dx, dy in zip(dxs, dys):	
		nx, ny = x + dx, y + dy
		if in_range(nx,ny) and matrix[nx][ny] not in set_alpha:
			set_alpha.add(matrix[nx][ny])
			dfs(nx,ny,cnt+1)
			set_alpha.remove(matrix[nx][ny])
		


r, c = tuple(map(int, input().split()))
matrix = [list(sys.stdin.readline().strip()) for _ in range(r)]
dxs, dys = [0,0,1,-1], [1,-1,0,0]
answer = 0
set_alpha = set()
set_alpha.add(matrix[0][0])
dfs(0,0,1)

print(answer)