BFS

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 처음에는 조합으로 풀면 되겠다 싶어서 풀었다. 계속 안 풀렸는데, 공집합인 경우도 있어서 depth 가 0보다 큰 경우에 카운팅 하도록 했다. 그리고 제출 후, 구글링을 해보니 다 나랑 다른 풀이로 풀었었다. 가장 이해가 되는 사진이 있어서 가져와보면, 재귀인 것은 똑같지만, 현재 값을 포함하는 경우와 포함하지 않는 경우로 트리 구조로 가져가서 풀었다. 두 풀이..

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net """ 빙산 (Gold 4) https://www.acmicpc.net/problem/2573 """ from collections import deque N, M = map(int, input().split()) # N * M 배열 board = [list(map(int, input().split())) for _ in range(N)] dd = [(-1, 0), (1, 0), (0, -1..

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net """ 적록색약 (Gold 5) https://www.acmicpc.net/problem/10026 """ from collections import deque N = int(input()) # N 입력받음. ( N * N ) board = [input() for _ in range(N)] # 적록색약 아닌 사람의 그래프 board_blind = [row.replace("R", "G") f..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net from collections import deque MAX_NUM = 100_001 # 위치값의 범위 0 ~ 100,000 N, K = map(int, input().split()) visited = [False] * MAX_NUM # 방문 여부 기록 sec_list = [0] * MAX_NUM # 각 좌표에 도달할 때의 시간 기록 def bfs(): # bfs..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net from collections import deque MAX_NUM = 100_001 # 위치값의 범위 0 ~ 100,000 N, K = map(int, input().split()) visited = [False] * MAX_NUM # 방문 여부 기록 sec_list = [0] * MAX_NUM # 각 좌표에 도달할 때의 시간 기록 def bfs(): # bfs로 한칸..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net from collections import deque N, M = map(int, input().split()) # N 행 M 열 입력 받기 adj = [list(map(int, input())) for _ in range(N)] # 미로 행렬 저장 visited = [[False] * M for _ in range(N)] # 미로 방문 행렬 저장 q = deque() # bfs용 큐 dx = [0, 0, -1, 1] dy = ..