문제 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/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 문제 해결방법 bfs 로 해결 가능 노드별로 방문 결과에 대해 방문결과 값을 업데이트 하고 방문결과가 있는 노드는 skip 하고 방문 안한 노드는 방문해서 총 몇번 반복 되는지 문제 풀이 import sys from collections import deque N, M = map(int, sys.stdin.readline().st..
문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 해결방법 bfs 로 해결 가능하다. 입력 조건으로 토마토는 1개이상이 들어갈수 있기 때문에 bfs 실행 전에 토마토의 위치를 큐에 넣어줘야 한다. 그 이후에 bfs 함수에서 인접열 방문시에 0(익지않은 토마토) 값이라면 기준열 토마토가 익는데 걸리시간에서 +1일을 해준다. bfs 종료 후 만약 graph 내에 0이 아닌 값이 있다면 -1로 인해서 인접열 방문 실패한 경우..
문제 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,..
문제 설명 1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.) 예를 들어 1234 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 가 있다면 가장 큰 정사각형은 1234 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다. 제한사항 표(board)는 2차원 배열로 주어집니다. 표(board)의 행(row)의 크기 : 1,000 이하의 자연수 표(board)의 열(column)의 크기 : 1,000 이하의 자연수 표(boar..
문제 설명 직사각형을 만드는 데 필요한 4개의 점 중 3개의 좌표가 주어질 때, 나머지 한 점의 좌표를 구하려고 합니다. 점 3개의 좌표가 들어있는 배열 v가 매개변수로 주어질 때, 직사각형을 만드는 데 필요한 나머지 한 점의 좌표를 return 하도록 solution 함수를 완성해주세요. 단, 직사각형의 각 변은 x축, y축에 평행하며, 반드시 직사각형을 만들 수 있는 경우만 입력으로 주어집니다. 제한사항 v는 세 점의 좌표가 들어있는 2차원 배열입니다. v의 각 원소는 점의 좌표를 나타내며, 좌표는 [x축 좌표, y축 좌표] 순으로 주어집니다. 좌표값은 1 이상 10억 이하의 자연수입니다. 직사각형을 만드는 데 필요한 나머지 한 점의 좌표를 [x축 좌표, y축 좌표] 순으로 담아 return 해주세요..
문제 설명 길이가 n인 배열에 1부터 n까지 숫자가 중복 없이 한 번씩 들어 있는지를 확인하려고 합니다. 1부터 n까지 숫자가 중복 없이 한 번씩 들어 있는 경우 true를, 아닌 경우 false를 반환하도록 함수 solution을 완성해주세요. 제한사항 배열의 길이는 10만 이하입니다. 배열의 원소는 0 이상 10만 이하인 정수입니다. 입출력 예 arrresult [4, 1, 3, 2] true [4, 1, 3] false 입출력 예 설명 입출력 예 #1 입력이 [4, 1, 3, 2]가 주어진 경우, 배열의 길이가 4이므로 배열에는 1부터 4까지 숫자가 모두 들어 있어야 합니다. [4, 1, 3, 2]에는 1부터 4까지의 숫자가 모두 들어 있으므로 true를 반환하면 됩니다. 입출력 예 #2 [4, 1..
