BFS

문제 https://www.acmicpc.net/problem/3055 풀이 입력으로 그래프가 주어지고, 어느 칸에서 BFS를 시작해야하는지 알려준다. 문제를 읽어보면 고슴도치와 물 둘 다 BFS 탐색을 해야 하는 것을 알 수 있다. 주의할 점은 예제에는 초기에 물인 칸이 1개밖에 없지만 문제를 읽어보면 1칸이라는 제약조건이 없다. 따라서 물이 여러칸일 때도 생각하고 프로그래밍을 해야 한다. 처음에 두 가지 생각을 했다. BFS탐색을 각각 따로 하는 방법 고슴도치를 먼저 BFS 탐색시켜서 그래프에 각 칸마다 몇번째 이동에 도달하는지 검사한다. 다음에 물을 BFS 탐색해서 1의 결과가 가능한지를 판단한다. 고슴도치와 물을 단계별로 번갈아가면서 BFS 탐색 하는 방법 ...

문제 https://www.acmicpc.net/problem/7576 풀이 처음엔 무난한 BFS 문제라고 생각했다. 처음부터 익어있는 토마토(루트 토마토라고 하겠다.)가 들어있는 칸을 알아낸 다음에 반복문으로 BFS를 적용하고, 루트 토마토를 할 때마다 만약 칸에 더 적은 숫자가 들어 갈 수 있다면 숫자를 업데이트 하는 식으로 문제를 풀었다. 그랬더니 시간초과가 나온다. 쓸데없는 연산이 너무 많아서 그렇다. 정확한 풀이는 BFS 큐를 처음 만들때부터 모든 루트 토마토를 넣어서 초기화 하는 것이었다. 그러면 모든 루트 토마토를 기준으로 동시에 탐색할 수 있으니까. 칸을 탐색할때도 더 높은 숫자가 나오면 그 칸은 큐에 넣을 필요가 없다. 이미 전에 했던 탐색이 더 좋은 결과를 가져다 주었을태니 ...

문제 https://www.acmicpc.net/problem/2667 풀이 그래프가 입력으로 주어지고, 각 노드마다 탐색의 범위가 상하좌우로 제한된다. 앞서 해결했던 미로 탐색과 순열 사이클을 섞어놓은 듯 한 문제이다. 따라서 다음과 같은 과정으로 출력값을 얻었다. 전체 그래프를 탐색하는 2중 반복문을 작성한다. 방문하지 않은 노드가 나올 때마다 그래프 탐색(DFS, BFS)를 실시한다. 각 그래프를 탐색했을때 노드의 개수를 저장하고 정렬한 다음에 출력한다. 코드 from collections import deque def bfs(v): bfsQ = deque() bfsQ.append(v) isVisited[v[0]][v[1]] = True moves = [(1, 0), (-1, 0), (0, 1), (0, -1)] count = 1 while bfsQ: node = bfsQ.popleft() for move in moves: row = node[0] + move[0] column = node[1] + move[1] if row < 0 or row >= n or column < 0 or column >= n: continue if graph[row][column] != 0 and not isVisited[row][column]: isVisited[row][column] = True bfsQ.append((row, column)) count += 1 return count n = int(input()) graph = [] for _ in range(n): temp = input() graph.append(list(map(int, temp))) isVisited = [[False] * n for i in range(n)] area = [] for row in range(n): for column in range(n): if graph[row][column] == 1 and not isVisited[row][column]: area.append(bfs((row, column))) area.sort() print(len(area)) for i in range(len(area)): print(area[i])

문제 https://www.acmicpc.net/problem/1697 풀이 입력으로 수빈이와 동생의 위치, 그리고 수빈이가 이동할 수 있는 제약조건을 알려준다. 수빈이의 위치보다 동생의 위치가 더 앞에 있거나 같을때는 (n >= k) 뒤로 가는 방법이 한칸 이동하는 것 밖에 없으므로 n - k 로 쉽게 결과를 도출 할 수 있다. 그 외의 경우에는 각각의 좌표를 노드라고 생각했을 때, 이 그래프는 각 노드가 노드값이 1만큼 크거나 작은 노드와 2배인 노드와 연결되어 있다. 따라서 BFS를 이용하면 쉽게 해결 할 수 있다. ...

문제 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()