문제 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제 풀이 import collections import sys dx = [-1, 0, 1, 1, 1, 0, -1, -1] dy = [-1, -1, -1, 0, 1, 1, 1, 0] def bfs(graph, y, x): graph[y][x] = 0 queue = collections.deque([(y, x)]) while queue: yy, xx = queue.popleft() for..

문제 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 문제 풀이 import collections import sys dx = [0, 1, 0, -1] dy = [-1, 0, 1, 0] N = int(sys.stdin.readline().strip()) MAX_VALUE, MIN_VALUE = 0, 0 maps = [] for _ in range(N): case = list(map(int, sys.stdin.readline().split())) MIN..

문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 풀이 import sys from collections import deque n, k = map(int, sys.stdin.readline().split()) MAX = (10 ** 5) def bfs(root, find): distance = [0] * (MAX+1) queue = deque([root]) while queue: x = queue.pople..

문제 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 import sys N = int(sys.stdin.readline()) maps = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] for k in range(N): for y in range(N): for x in range(N): if maps[y][k] and maps[k][x]: maps[y][x] = 1 for m in maps: print(' ..

문제 https://www.acmicpc.net/problem/9372 문제 풀이 import collections import sys T = int(sys.stdin.readline()) def bfs(graph, i, visited, count): # visited[i] = 1 queue = collections.deque([i]) while queue: node = queue.popleft() if visited[node] == 0: visited[node] = 1 count += 1 queue.extend(graph[node]) return count for _ in range(T): N, M = map(int, sys.stdin.readline().split()) graph = [[] for _..

문제 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 풀이 import collections import sys M, N, H = map(int, sys.stdin.readline().split()) tomato = [[] for _ in range(H)] queue = collections.deque([]) for h in range(H): for y in range(N): temp = list(map(int, s..

문제 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 해결방법 bfs 로 해결 가능 graph[y][x] == 1 인 곳에서 검색을 시작하여 인접한 부분을 모두 0으로 변경한 뒤에 count++ 문제 풀이 import sys from collections import deque T = int(sys.stdin.readline().strip()) dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] for _ in range(T): M, ..

문제 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 해결방법 bfs 로 해결 가능 graph[i][j] 가 1인 곳에서 검색을 시작해서 인접한 부분을 찾고 종료시 count return 문제 풀이 import sys from collections import deque N = int(sys.stdin.readline().strip()) boards = [] for _ in range(N): boards.append(list(map(int,..