BFS

[BFS, 시뮬레이션, 배열 회전] BOJ 20058 마법사 상어와 파이어스톰

2차원 배열 회전 방식을 알고 있어야 풀 수 있는 문제. 해당 문제는 시계방향 90도지만 180, 270 + 반시계방향에 대해서도 숙지하는 것이 좋을 것 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 from typing import List from collections import deque N, Q = map(int, inpu..

[BFS, 시뮬레이션] 14500 테트로미노

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 import sys input = sys.stdin.readline N, M = map(int, input().split()) board..

[시뮬레이션, BFS] BOJ 16236 아기상어

https://www.acmicpc.net/problem/16236 시뮬레이션 + dfs + dp(visited) 살짝 가미된 형태로 구현하였다. 여기서 주의할 점은 잡아먹는 물고기의 크기는 1 ~ 6이라면 커지는 상어의 크기는 무한하다는 것. size로 제한하면 초반엔 괜찮지만 상어의 크기가 9이상이 되면 무한 반복이 일어나 시간초과가 발생할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 ..

[BFS] BOJ 7576 토마토

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 import sys from collections import deque input = sys.stdin.readline M, N = map(int, input().split()) box = [list(map(int, input().split())) for _ in range(N)] DELTAS = ((1, 0), (0, 1), (-1, 0), (0, -1)) visited = [[-1] * M for _ in range(N)] def bfs(arr, visited): queue = de..

[BFS] BOJ 7569 토마토

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 import sys from collections import deque input = sys.stdin.readline M, N, H = map(int, input().split()) def dfs(points): visited = [[[-1] * M for _ in range(N)] for _ in range(H)] for h, y, x in points: visited[h][y][x] = 0 DELTAS..

[BFS] BOJ 2206 벽 부수고 이동하기

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 import sys from collections import deque input = sys.stdin.readline N, M = map(int, input().split()) arr = [input().split() for _ in range(N)] arr = list(list(map(int, list(a[0]))) for a in arr) visited = [[[0, 0] for _ in range(M)] for _ in range(N)] # BFS 방법 DELTAS = ((0, 1), (1, 0), ..

[BFS, DFS] BOJ 1697 숨바꼭질

보호되어 있는 글입니다.

[DFS, BFS] BOJ 1012 유기농 배추

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 import sys from collections import deque input = sys.stdin.readline T = int(input()) points = ((1, 0), (-1, 0), (0, 1), (0, -1)) for _ in range(T): M, N, K = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(K)] graph = [[0] * M for _ in range(N)] for x, y ..

[DFS, BFS] 2667 단지 번호 붙이기

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 import sys from collections import deque input = sys.stdin.readline N = int(input()) arr = [list(map(int, input().strip())) for _ in range(N)] visited = [[0] * N for _ in range(N)] graph = [] points = ((1, 0), (-1, 0), (0, 1), (0, -1)) color = 0 for i in range(N): for j in range(N): q =..

[Graph, DFS, BFS] BOJ 2606 바이러스

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 import sys from collections import deque input = sys.stdin.readline N = int(input()) E = int(input()) arr = [list(map(int, input().split())) for _ in range(E)] graph = [[] for _ in range (N+1)] for start, end in arr: graph[start].append(end) graph[end].append(start) result = 0 visited = [0] * (N+1) q = deque() q.append(1)..

[Graph, DFS, BFS] BOJ 1260 DFS와 BFS

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 import sys from collections import deque input = sys.stdin.readline N, M, V = map(int, input().split()) arr = list(map(int, input().split()) for _ in range(M)) # graph 생성 graph = [[] for _ in range(N+1)] for start, end in arr: graph[start].append(end) gr..