BFS 23

[baekjoon] 백준 16236번 : 아기 상어 (by python 파이썬) bfs, lambda정렬

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 정답 code #아기 상어 from collections import deque import sys input = sys.stdin.readline dx = [-1,1,0,0] dy = [0,0,1,-1] def bfs(x,y,shark_size): distance = [[0]*n for _ in range(n)] #거리 저장 visit = [[0]*n for _ in range(n)] #..

[baejoon] 백준 14500번 : 테트로미노 (by python 파이썬) BFS

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 정답 code #테트로미노 import sys input = sys.stdin.readline def dfs(r,c,bcount,total): global ans #종료조건1 - 최댓값에 못미치는 경우 if ans >= total + max_value * (3-bcount): return #종료조건2 - 블럭 4개를 모두 활용한 경우 if bcount == 4: ans = max(ans, tota..

[baekjoon] 백준 11403번 : 경로 찾기 (by python) 플로이드-워셜

https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 정답 code #경로 찾기 n = int(input()) graph = [] for i in range(n): graph.append(list(map(int,input().split()))) for k in range(n): for i in range(n): for j in range(n): if (graph[i][k] == 1 and graph[k][j] == 1): graph[i][j] = 1 for i in graph: for j i..

[baekjoon] 백준 10026번 : 적록색약 (by python) bfs dfs

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 정답 code -bfs활용 #적록색약 from collections import deque import sys input = sys.stdin.readline dx = [-1,1,0,0] dy = [0,0,-1,1] def bfs(x,y): q.append([x,y]) visit[x][y] = cnt while q: x, y = q.popleft() for i in range(4): nx ..

[baekjoon] 백준 9019번 : DSLR (by python) bfs *pypy3

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 정답 code # DSLR from collections import deque import sys input = sys.stdin.readline t = int(input()) for _ in range(t): a,b = map(int,input().split()) q = deque() q.append((a,"")) visit = [False]*10000 while q: num, p..

[baekjoon] 백준 7569번 : 토마토 (by python) bfs 너비우선 탐색

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 정답 code #토마토 from collections import deque import sys input = sys.stdin.readline dx = [-1,1,0,0,0,0] dy = [0,0,-1,1,0,0] dz = [0,0,0,0,-1,1] queue = deque() m , n , h = map(int,input().split()) box = [] for i i..

[baekjoon] 백준 11724번 : 연결 요소의 개수 (by python) dfs,bfs

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 정답 code -DFS풀이 #연결 요소의 개수 import sys sys.setrecursionlimit(5000) input = sys.stdin.readline #dfs풀이 def dfs(x): visited[x] = True for i in c[x]: if not visited[i]: dfs(i) n, m = map(int,inp..

[baekjoon] 백준 7576번 : 토마토 (by python) with 너비 우선 탐색 bfs

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 정답 code #토마토 import sys from collections import deque input = sys.stdin.readline dx = [-1,1,0,0] dy = [0, 0 , -1, 1] def bfs(): while queue: x, y = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] i..

[baekjoon] 백준 2606번 : 바이러스 (by python 파이썬) bfs dfs 두가지 풀이

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 정답 code -dfs 활용 #dfs이용 def dfs(com, x): global cnt visited[x] = True for i in com[x]: if visited[i] == False: dfs(com,i) cnt += 1 return True n = int(input()) c = int(input()) cnt = 0 com = [[] for _ in range(n+1)] for _ in ra..

[baekjoon] 백준 2178번 : 미로 탐색 (by python 파이썬) with bnf

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 정답 code #미로 탐색 from collections import deque def bfs(x,y): dx = [-1,1,0,0] dy = [0,0,-1,1] queue = deque() queue.append((x,y)) while queue: x, y = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if nx =n or ny= m: continue i..