1. DFS 구현DFS는 stack으로 구현되며 재귀 함수를 통해 구현할 수 있다.import sysinput = sys.stdin.readlinedef dfs(now, graph, visited): visited[now] = True print(now, end=' ') for next in graph[now]: if not visited[next]: dfs(next, graph, visited)n, m, start_node = map(int, input().rstrip().split()) graph = [[] for _ in range(n+1)] ..
Algorithm/Graph
알파벳을 탐색할 때 고려해야할 조건은 다음과 같다. 다음에 탐색하는 인덱스가 배열 범위를 넘어가는가? 다음 알파벳을 이전에 만난적이 있는가? 위를 고려하여 DFS 방식으로 탐색하면 다음과 같이 구현할 수 있다. import sys input = sys.stdin.readline def dfs(x, y, tmp): # 현재까지 탐색한 결과가 최대 이동 횟수라면 result에 저장한다. global result result = max(result, tmp) # 현재 위치에 해당하는 알파벳에 방문처리를 한다. index = ord(board[x][y])-ord("A") visited[index] = True # 모든 방향으로 이동하여 dfs 탐색을 수행한다. for i in range(4): next_x, n..
