📌 문제 제목문제 링크: 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..

📌 문제 제목문제 링크: BOJ 2178🗒️ 문제 설명NxM 크기의 배열로 표현되는 미로가 있다.미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다.(1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램.시간 제한: 1초메모리 제한: 192MB2 💡 문제 해결 아이디어NM이 10,000 이기 때문에 O(NM)의 시간복잡도를 가지는 알고리즘 사용.BFS를 사용해서 각 칸과 시작점 사이의 거리를 구할 수 있다.⌛️ 시간 복잡도O(NM)✅ 최종 코드import sysfrom collections import dequeinput = sys.stdin.readlineN, M = map(int, input().split())graph..

📌 문제 제목문제 링크: BOJ 1926🗒️ 문제 설명어떤 도화지에 그림이 그려져 있을 때, 그 그림의 개수와 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라.단, 그림이라는 것은 1로 연결된 것을 그림이라고 정의한다.시간 제한: 2초메모리 제한: 128MB세로 크기: 1 가로 크기: 1 💡 문제 해결 아이디어NM이 250,000 이므로 O(NM)의 시간복잡도를 가진 알고리즘을 사용하면 해결 가능.이차원 배열을 순회하며 그림의 시작점을 찾고 BFS로 그림의 개수와 넓이를 구한다.그림의 개수는 이차원 배열을 돌며 BFS를 수행할 때마다 count를 증가시킨다.그림의 넓이는 BFS의 리턴값을 해당 그림의 넓이로 하고, BFS가 끝나면 해당 그림의 넓이와 이전에 저장해둔 그림의 최대 넓이를 비교한다..