[백준] 1987: 알파벳

백트래킹

알파벳

DFS 와 BFS로 모두 풀 수 있는 문제입니다.
백트래킹의 개념을 잘 알 수 있는 문제였습니다.
처음에 BFS로 풀다가 계속 시간초과 나서 진짜 인내심의 한계를 느꼈습니다
BFS로 풀거면 중복 처리 잘 해야하니 유념하세요 하 ㅋ
DFS는 딱 백트래킹 이였습니다.
방문 처리 한 것을 현재 돌고 있는 DFS가 끝나면 원복하기

DFS도 다음 것이 영향이 있으면 무조건 방향 배열 만들자!

DFS

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
graph = []
for i in range(n):
	graph.append(list(sys.stdin.readline().rstrip()))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
result = -1
def dfs(x, y, cnt):
	global result
	for i in range(4):
		nx = x + dx[i]
		ny = y + dy[i]
		if nx < 0 or ny < 0 or nx >= n or ny >= m:
			continue
            	# 내가 가려는 알파벳 방문 안했으면 방문 처리 해주고 dfs
		if not visited[ord(graph[nx][ny])-65]:
			visited[ord(graph[nx][ny])-65] = True
			dfs(nx, ny, cnt+1)
            		# 이것이 백트래킹이다 다시 돌아와 그리고 다른 방향 가셈
			visited[ord(graph[nx][ny])-65] = False
            	# cnt 는 계속 큰 값으로 갱신해주기 
		result = max(result, cnt)
	return result
# 알파벳 방문했나요? 알파벳 배열 생성 
visited = [0] * 27
#현 알파벳 방문이요 ㅋ
visited[ord(graph[0][0])-65] = True
# x, y, cnt
print(dfs(0, 0, 1))

BFS

최단 경로를 구하는 문제가 아니라서 deque 말고 set으로 풀어도 됨
(시간 초과 안나려면 이 문제에서는 set이 필수 )
set 은 pop and add

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
graph = []
for i in range(n):
	graph.append(list(sys.stdin.readline().rstrip()))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs():
	visited = [[False] *m for _ in range(n)]
	result = 1
    	# 여기서 경로가 달라도 graph 배열에 따라 visit, nx, ny가 같아질 수 있음 
	q = set([(0, 0, graph[0][0])])
	while q:
		x, y, visit = q.pop()
		for i in range(4):
			nx = x + dx[i]
			ny = y + dy[i]
			if nx < 0 or ny < 0 or nx >= n or ny >= m:
				continue
			if graph[nx][ny] == graph[x][y]:
				continue
			if graph[nx][ny] not in visit:
				q.add((nx, ny, visit + graph[nx][ny]))
				result = max(result, len(visit + graph[nx][ny]))
	return result
print(bfs())

~~오히려 좋아 백트래킹 잘 알았어 ~~