와구와구

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PobmqAPoDFAUq SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com BFS 활용시작점은 무조건 (0, 0)달팽이 무빙은 오른쪽, 아래, 왼쪽, 위쪽 순으로 이루어진다.그래서 direction 리스트에 방향을 튜플로 순서대로 저장해준다.direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]d = 0 # 현재 움직일 방향이후 BFS를 direction에 따라 시행한다.방향은 현재 direction에 따른 다음 위치가 map 크기를 넘어섰거나, ..

https://www.acmicpc.net/problem/11725 입력으로 주어지는 것들이, '처음에 나오는 것이 부모다'라는 말이 없어서 undirectional graph로 트리를 생성했다.노드 1이 항상 루트이므로, 노드 1에서부터 BFS를 수행하며 노드의 부모를 찾는 것을 목표로 했다. # https://www.acmicpc.net/problem/11725# Tree, BFSimport sysfrom collections import defaultdict, dequeN = int(input())tree = defaultdict(list)for _ in range(N-1) : a, b = map(int, sys.stdin.readline().split()) tree[a].append(b..

https://www.acmicpc.net/problem/7569 3차원 배열에서의 BFS문제 기존에 defaultdict을 활용한 Graph를 중심으로 탐색을 진행했었는데, 이번엔 메모리 초과 문제로 사용을 포기했다.대신 BOX와 visited를 적극 활용하여 defaultdict을 대신했다.토마토가 다 익는데 필요한 시간은 visited에 적어 최대한 메모리 사용을 줄였다. 조건이 몇 개 있다. 토마토가 모두 익지 못하는 경우, 애초에 토마토가 모두 익어 있는 경우에 다른 수를 출력해야 한다.이를 위해 green_tomatos라는 변수를 둬서 BFS 중 익을 경우 요소를 제거하는 방식으로 안 익은 토마토를 바로 확인할 수 있도록 했다.또한 처음 BFS를 시작하기 전 green_tomatos의 요소 갯..

https://www.acmicpc.net/problem/10026 # https://www.acmicpc.net/problem/10026# BFSfrom collections import deque, defaultdictN = int(input())MAP = []RGB = defaultdict(list)for n in range(N+2) : if n == 0 or n == N+1 : MAP.append('0'*(N+2)) continue line = input() for idx, l in enumerate(line) : if l == 'R' : RGB['R'].append((n-1, idx)) elif l == 'G'..

https://www.acmicpc.net/problem/14502 # https://www.acmicpc.net/problem/14502# BFSimport sysfrom collections import defaultdict, dequeimport itertoolsN, M = map(int, sys.stdin.readline().split())MAP = [[1 for _ in range(M+2)] for _ in range(N+2)]virus = []empty = []wall = []for n in range(1, N+1) : line = list(map(int, sys.stdin.readline().split())) for idx, l in enumerate(line) : i..

https://www.acmicpc.net/problem/1697 아이디어기존 BFS 그래프 탐색을 X-1, X+1, 2*X로 대체한다# https://www.acmicpc.net/problem/1697# BFSimport sysfrom collections import dequeN, K = map(int, sys.stdin.readline().split())def BFS(N, K) : visited = [-1 for _ in range(100001)] q = deque([N]) visited[N] = 0 while q : u = q.popleft() if u == K : print(visited[u]) brea..

https://www.acmicpc.net/problem/7576 # https://www.acmicpc.net/problem/7576# BFSimport sysfrom collections import defaultdict, dequeimport itertoolsM, N = map(int, sys.stdin.readline().split())MAP = [[2 for _ in range(M+2)] for _ in range(N+2)]red_tomatos = []empty = []for n in range(1, N+1) : MAP[n][1:M+1] = list(map(int, sys.stdin.readline().split())) for m, tomato in enumerate(MAP[n][1..

https://www.acmicpc.net/problem/1012 문제는 저번에 푼 것과 다를 게 없는데 자꾸 원하지 않는 답이 나와서 왜 그런지 분석하느라 오래걸렸다.MAP 정보를 전부 입력한 후 graph 생성을 했어야 했는데 for문에서 돌면서 MAP 정보를 입력하면서 graph 생성을 해서올바른 graph가 생성되지 않았었다.. 이 문제를 해결하는 데에 2시간이나 걸렸다... # https://www.acmicpc.net/problem/1012# BFSimport sysfrom collections import defaultdict, dequeT = int(input())dx = [0, 0, -1, 1] # 상 하 좌 우dy = [-1, 1, 0, 0] # 상 하 좌 우def BFS(start, ..

https://www.acmicpc.net/problem/2667 이 문제를 풀기 위한 아이디어를 다음과 같이 설정했다.1. BFS를 사용한다2. 그래프를 생성한 후, 모든 노드마다 방문한 적이 없다면 해당 노드를 start로 설정하여 BFS를 수행한다 그리고 단지 별 단지 수는 dictionary를 사용하여 답을 내도록 했다.# https://www.acmicpc.net/problem/2667# BFSimport sysfrom collections import defaultdict, dequeN = int(input())MAP = []graph = defaultdict(list)for i in range(N) : MAP.append(input())# graph 만들기for i in range(N)..

https://www.acmicpc.net/problem/2606 감염을 '연결된 노드 탐색'으로 해석하여 BFS로 풀이했다.# https://www.acmicpc.net/problem/2606# BFSimport sysfrom collections import defaultdict, dequenum_com = int(input())num_edges = int(input())graph = defaultdict(list)for _ in range(num_edges) : a, b = map(int, sys.stdin.readline().split()) graph[a].append(b) graph[b].append(a)def BFS(graph) : visited = [0 for _ in..