문제 https://www.acmicpc.net/problem/2178 풀이 입력값으로 미로의 크기와 구성이 주어진다. 미로 안에서는 값이 1인 칸으로만 이동 할 수 있고, 또 각 칸에서는 상하좌우의 칸으로밖에 이동하지 못한다. -> 현재 칸에서 상하좌우의 칸을 탐색해서 1인 경우에만 Queue에 넣는다. 이 문제에서는 각 노드를 방문했는지의 여부보다 몇번째에 방문했는지의 여부가 더 중요하다. -> 이전 노드의 방문 순서에 1을 더한 값을 현재 노드의 방문 순서로 한다. (isVisited가 Bool이 아닌 Integer로 구현된다) 이렇게 얻어낸 두가지 인사이트로 BFS를 구현한다. 코드 from collections import deque def bfs(location): visit = [[0] * m for _ in range(n)] bfsQ = deque() bfsQ.append(location) visit[0][0] = 1 while bfsQ: node = bfsQ.popleft() up = [node[0] - 1, node[1]] down = [node[0] + 1, node[1]] left = [node[0], node[1] - 1] right = [node[0], node[1] + 1] moves = [up, down, left, right] for i in range(len(moves)): x = moves[i][0] y = moves[i][1] if x < 0 or y < 0 or x >= n or y >= m: continue if maze[x][y] == "0": continue if visit[x][y] == 0: visit[x][y] = visit[node[0]][node[1]] + 1 bfsQ.append([x, y]) return visit[n - 1][m - 1] maze = [] n, m = map(int, input().split()) for i in range(n): temp = list(input()) maze.append(temp) print(bfs([0, 0])) 시작 노드와 종료 노드가 명확하게 정해져 있으므로 DFS로도 풀릴것이라는 생각이 든다.

문제 https://www.acmicpc.net/problem/1260 풀이 심플하다. 입력값으로 그래프가 주어지고, DFS와 BFS를 이용해 탐색한 결과를 각각 출력하면 된다. 코드 from collections import deque def dfs(v, dfsArray): isVisitedDFS[v] = True dfsArray.append(v) for i in range(len(graph[v])): if graph[v][i] != 0 and isVisitedDFS[i] == False: dfs(i, dfsArray) def bfs(v, bfsArray): QueueBFS = deque() isVisitedBFS[v] = True QueueBFS.append(v) while len(QueueBFS) != 0: node = QueueBFS.popleft() bfsArray.append(node) for i in range(len(graph[node])): if graph[node][i] != 0 and not isVisitedBFS[i] QueueBFS.append(i) isVisitedBFS[i] = True n, m, v = map(int, input().split()) graph = [[0] * (n + 1) for i in range(n + 1)] isVisitedDFS = [False for i in range(n + 1)] isVisitedBFS = [False for i in range(n + 1)] dfsArray = [] bfsArray = [] for i in range(m): a, b = map(int, input().split()) graph[a][b] = graph[b][a] = 1 dfs(v, dfsArray) bfs(v, bfsArray) for node in dfsArray: print(node, end=" ") print() for node in bfsArray: print(node, end=" ") print()

문제 https://www.acmicpc.net/problem/10451 풀이 순열이 각각의 (1부터 시작하는)인덱스와 매칭되어있는 그래프를 만들면 쉽게 해결된다. (친절하게 문제에 그림도 있다.) 순열과 인덱스는 내부 원소들이 순서를 제외하고 같으므로 무조건 내부에 사이클을 형성하게 된다. 따라서 문제에서 주어진 그대로 우리는 서로 가르키는 방향을 재귀로 따라가고, 이미 방문한 숫자가 나온다면 재귀를 종료시키기를 반복해서 생기는 사이클의 총 개수를 카운트 하기만 하면 된다. 코드 def dfs(v, start): isVisited[v] = True if not isVisited[permutation[v - 1]]: dfs(permutation[v - 1], start) n = [] per = [] t = int(input()) for _ in range(t): n_temp = int(input()) per_temp = list(map(int, input().split())) n.append(n_temp) per.append(per_temp) for case in range(t): count = 0 isVisited = [False] * (n[case] + 1) permutation = per[case] for i in range(1, n[case] + 1): if not isVisited[i]: dfs(i, i) count += 1 print(count) 굳이 재귀를 쓰지 않더라도 반복문만으로도 깔끔한 코드가 나올것 같다.