📌 문제 제목문제 링크: BOJ 11286🗒️ 문제 설명절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.배열에 정수 x (x != 0)을 넣는다.배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러 개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.프로그램은 처음에 비어있는 배열에서 시작한다.N번 연산을 수행하며 x가 0이 아니라면 배열에 x라는 값을 추가하고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거한다.시간 제한: 1초메모리 제한: 256MB💡 문제 해결 아이디어x가 0이 아닌 정수라면 배열에 x를 추가x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 제거한다.heapq를 (|x..

📌 문제 제목문제 링크: BOJ 14500 🗒️ 문제 설명폴리오미노란 크기가 1x1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.정사각형은 서로 겹치면 안된다.도형은 모두 연결되어 있어야 한다.정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.크기가 NxM인 종이 위에 테트로미노 하나를 놓으려고 한다.종이는 1x1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여있다.테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여있는 수들의 합을 최대로 하는 프로그램을 작성하여라.시간 제한: 2초메모리 제한: 512MB세로 크기 N,..

📌 문제 제목문제 링크: BOJ 2583🗒️ 문제 설명M x N 크기의 모눈종이가 있을 때, 이 모눈종이 위에 K개의 직사각형을 그리고 남은 부분의 영역 개수와 크기를 구하여라시간 제한: 1초메모리 제한: 128MB1 💡 문제 해결 아이디어M x N 크기의 True 값을 가지는 graph 배열을 만든다.K번 직사각형을 만드면서 graph에 False 값을 넣는다.BFS를 수행하며 영역의 크기와 개수를 구한다.⌛️ 시간 복잡도O(M x N + K)✅ 최종 코드import sysfrom collections import dequeinput = sys.stdin.readlineM, N, K = map(int, input().split())graph = [[True] * N for _ in range(M)..

📌 문제 제목문제 링크: BOJ 7562🗒️ 문제 설명체스판 위에 한 나이트가 놓여져 있다. 나이트가 이동하려고 하는 칸이 주어진다.나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?💡 문제 해결 아이디어나이트의 이동 direction을 정의dist 배열을 만들어서 이동한 적 없는 좌표에 대해서만 움직인다.⌛️ 시간 복잡도O(T x L^2)✅ 최종 코드import sysfrom collections import dequeinput = sys.stdin.readlineT = int(input().strip())direction = [(-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1)]def bfs(s_..

📌 문제 제목문제 링크: BOJ 7569🗒️ 문제 설명보관 후 하루가 지나면 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램.시간 제한: 1초메모리 제한: 256MB2 1 💡 문제 해결 아이디어3중 for문을 돌며 토마토가 있는 좌표를 큐에 저장한다.상하좌우위아래를 확인하며 익지 않은 토마토가 있으면 큐에 넣는다.3중 for문을 돌며 익지 않은 토마토가 있는지 확인하면서 dist의 max값을 확인한다.⌛️ 시간 복잡도O(H x N x M)✅ 최종 코드import sysfrom collections import dequeinput = sys.stdin.readlineM, N, H = m..

📌 문제 제목문제 링크: BOJ 10026🗒️ 문제 설명R, G, B로만 칠해진 N x M 크기의 그림이 있다.적록색약인 사람이 봤을 때 그림의 구역의 수와 적록색약이 아닌 사람이 봤을 때 구역의 수를 구하여라.시간 제한: 1초메모리 제한: 128MB1 💡 문제 해결 아이디어그래프를 적록색약인 사람과 적록색약이 아닌 사람 두 개로 만들어서 풀면 된다.인풋이 R, G, B가 모두 있는 그림이므로 이중 for문을 돌면서 R와 G을 T로 둔 적록색약형 그림을 그린다.적록색약형 그림과 적록색약이 아닌 형 그림을 BFS로 돌면서 구역의 개수를 구한다.BFS에 color를 매개변수로 넘겨서 상하좌우에 color가 같고 아직 방문하지 않았으면 큐에 추가⌛️ 시간 복잡도O(N^2)✅ 최종 코드import sysf..

📌 문제 제목문제 링크: BOJ 1012🗒️ 문제 설명배추밭에 배추흰지렁이를 둬서 해충을 잡아먹게 하려고 한다.배추흰지렁이는 인접한 다른 배추로 이동할 수 있다.배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 된다.총 몇 마리의 지렁이가 필요한 지 출력하라.시간 제한: 1초메모리 제한: 512MB1 1 1 💡 문제 해결 아이디어BFS를 한번 돌 때 인접한 배추를 다 돌기 때문에 BFS 한번에 지렁이 한 마리가 필요.⌛️ 시간 복잡도O(T x (N x M + K))✅ 최종 코드import sysfrom collections import dequeinput = sys.stdin.readlineT = int(input().strip())direction = [(-1, 0), (1, 0), (0,..

📌 문제 제목문제 링크: BOJ 1697🗒️ 문제 설명수빈이는 현재 점 N (0 수빈이는 걷거나 순간이동 할 수 있다.수빈이의 위치가 X일 때, 1초 후에 X-1 or X+1 or 2*X로 이동할 수 있다.💡 문제 해결 아이디어수빈이의 좌표 N을 큐에 넣는다.for 문에 걷기와 순간이동한 결과를 넣는다.큐에 popleft를 할 때 K와 같으면 dist[K]를 출력한다.⌛️ 시간 복잡도O(N)✅ 최종 코드import sysfrom collections import dequeinput = sys.stdin.readlineN, K = map(int, input().split())queue = deque([N])dist = [-1] * 100_001dist[N] = 0while queue: nx = ..

📌 문제 제목문제 링크: BOJ 4179🗒️ 문제 설명미로에 지훈이와 불이 난 위치, 벽이 존재할 때, 지훈이를 탈출시켜야 한다.지훈이와 불은 매 분 상하좌우로 이동한다.지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.시간 제한: 1초메모리 제한: 256MB1 💡 문제 해결 아이디어이차원 for 문을 돌며 지훈이와 불이 있는 위치를 알아야 함.지훈이와 불의 위치를 각 큐를 만들어 넣고 dist 배열도 각자 만들어서 0으로 초기화 시킨다.불 BFS를 먼저 수행한다.지훈이 BFS를 수행하며 불이 오기 전에 갈 수 있으면 이동한다.그래프를 빠져나갈 수 있으면 jihun_dist[xp][yp] + 1을 출력한다.아니라면 IMPOSSIBLE을 출력한다.⌛️ 시간 복잡도O(RC)✅ 최종 코드impor..

📌 문제 제목문제 링크: BOJ 7576🗒️ 문제 설명토마토를 격자 모양의 상자에 보관한다.익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶다.시간 제한: 1초메모리 제한: 256MB2 💡 문제 해결 아이디어이차원 for 문을 돌며 초기에 익은 토마토들의 위치를 큐에 저장한다.큐가 빌 때 까지 BFS를 수행한다.이차원 for문을 돌며 dist의 최대값을 구한다.이차원 for문을 돌 때 dist가 -1이면서 익지 않은 토마토가 있으면 -1을 출력한다.⌛️ 시간 복잡도O(NM)✅ 최종 코드import sysfrom collections import dequeinput = sys.stdin.re..