![]()
백트래킹을 이용한 문제 다른게 아니라 알파벳으로 방문표기를 하다보니 여간 어려운게 아니었다. vis를 26개의 배열로 설정해 ord를 사용, 알파벳마다 하나씩 칸을 설정해 방문표기했다. 나머지는 그냥 백트래킹으로 해결했다. import sys input=sys.stdin.readline def dfs(x,y,cnt): global M vis[ord(m[x][y])-65]=1 M=max(M,cnt) dx=[-1,1,0,0] dy=[0,0,-1,1] for i in range(4): X=x+dx[i] Y=y+dy[i] if 0
![]()
백트래킹 문제. dfs로 돌려서 경로를 s에 튜플 형태로 모두 저장했다. 그 후에 s를 set으로 바꿔서 중복을 제거하고 갯수를 세어주면 오케이 #https://www.acmicpc.net/problem/17255 from collections import deque def dfs(start,end,res): vis=deque(res[-1]) if len(vis)==len(l): s.append(tuple(res)) return if start-1>=0: vis.appendleft(l[start-1]) res.append(tuple(vis)) dfs(start-1,end,res) vis.popleft() res.pop() if end+1
