문자
자체에 표시를 해두는 것이 더 좋다.<순서>
1.문자
를 숫자로 치환해둔다.
2. 치환한 숫자를 이용해 최대로 갈 수 있는 길을 찾는다.
import sys
r, c = map(int,sys.stdin.readline().split())
arr = [ list(map(lambda x: ord(x) - ord('A'),sys.stdin.readline().strip())) for _ in range(r)]
#print(arr)
mx = -1
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def dfs(x, y, index):
global mx
mx = max(index, mx)
for k in range(4):
tx = x + dx[k]; ty = y + dy[k]
if 0 <= tx < c and 0 <= ty < r:
tmp = arr[ty][tx]
if ch[tmp] == 0:
#print(arr[ty][tx])
ch[tmp] = 1
dfs(tx, ty, index+1)
ch[tmp] = 0
ch = [0]*(r*c)
ch[arr[0][0]] = 1
dfs(0, 0, 1)
print(mx)
set
와 tuple
을 이용해 집합을 구성했다.set
에 들어간 값은 다시 선택될 수 없다.def BFS(x, y):
global answer
q = {(x, y, board[x][y])}
while q:
x, y, ans = q.pop()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < R and 0 <= ny < C and board[nx][ny] not in ans:
q.add((nx,ny,ans + board[nx][ny]))
answer = max(answer, len(ans)+1)
R, C = map(int, sys.stdin.readline().split())
board = [[sys.stdin.readline().strip()] for _ in range(R)]
answer = 1
BFS(0, 0)
print(answer)
BFS
, DFS
풀이 방식에 대해 기억해두자.