728x90 반응형 Python/백준26 백준 연구소 [14502] 파이썬(Python) 코드 + 해설 #완전 탐색과 BFS 이 문제는 바이러스가 유출된 연구소에서 벽을 세워 바이러스의 확산을 막고, 안전 영역의 최대 크기를 구하는 것이 목표이다.문제 설명연구소 지도: N x M 크기의 직사각형이며, 각 칸은 다음 중 하나이다:빈 칸: 0벽: 1바이러스: 2바이러스 확산: 바이러스는 상하좌우로 인접한 빈 칸으로 퍼져나간다.벽 세우기:새로 세울 수 있는 벽의 개수는 정확히 3개이다.벽은 빈 칸에만 세울 수 있다.목표: 벽을 적절히 세워서 안전 영역(바이러스가 퍼질 수 없는 영역)의 크기를 최대로 만드는 것이다.해결 방법: 완전 탐색과 BFS 사용이 문제는 다음과 같은 방법으로 해결할 수 있다:모든 벽 세우기 경우의 수를 탐색한다:빈 칸 중에서 3개를 선택하여 벽을 세우는 모든 조합을 생성한다.N과 M이 최대.. 2024. 10. 24. 백준 퇴사 [14501] Python 코드 + 해설 문제 설명 1상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일2일3일4일5일6일7일TiPi35112421020102015402001일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.상담을 하는데 필요한 기간은 1일보다.. 2024. 10. 23. 백준 테트로미노 [14500] Python 코드 + 해설 백준 테트로미노 14500 파이썬(python) 코드 및 해설입니다.( DFS와 브루트 포스 ) **DFS(깊이 우선 탐색)**를 사용하여 모든 가능한 모양을 탐색한다.'ㅗ' 모양은 DFS로 탐색할 수 없으므로 별도로 처리한다.경계 조건을 명확히 확인하여 인덱스 오류를 방지한다.최적화를 위해 가지치기를 사용한다.구현 단계입력 받기종이의 크기 N, M과 종이에 쓰인 수들을 입력받는다.종이의 정보를 2차원 리스트 board에 저장한다.DFS 함수 구현현재 위치에서 깊이 4까지 탐색하여 가능한 모든 모양의 합을 계산한다.이미 방문한 위치를 재방문하지 않도록 visited 배열을 사용한다.백트래킹을 통해 방문 상태를 원래대로 복구한다.가지치기를 위해 남은 칸에서 얻을 수 있는 최대 값을 미리 계산하여 합산해도 .. 2024. 10. 22. 백준 주사위 굴리기 [14499] Python 코드 + 해설 백준 주사위 굴리기 14499 파이썬(Python) 정답 코드 및 해설입니다.이 문제에서는 N x M 크기의 지도 위에 주사위가 놓여 있고, 주어진 명령에 따라 주사위를 굴리면서 특정 규칙에 따라 지도의 숫자와 주사위의 숫자를 변경한다.주사위의 초기 상태와 전개도주사위의 초기 전개도는 다음과 같다: 24 1 3 5 6윗면: 1아랫면: 6앞면: 5뒷면: 2왼쪽 면: 4오른쪽 면: 3주사위의 모든 면에는 처음에 0이 적혀 있다.이동 규칙주사위를 이동시킨다.이동 방향은 동쪽(1), 서쪽(2), 북쪽(3), 남쪽(4)이다.주사위를 이동시킬 때 지도의 바깥으로 이동하려고 하면 그 명령은 무시한다.이동한 칸에 쓰여 있는 수에 따라 다음을 수행한다:칸의 수가 0이면: 주사위의 바닥면에 쓰여 있는 수를 칸에 복사.. 2024. 10. 22. 백준 시험 감독 [13458] Python 코드 + 해설 이 문제에서는 여러 시험장이 있고, 각 시험장마다 응시자의 수가 주어진다. 각 시험장에는 반드시 총감독관이 1명 있어야 하며, 총감독관은 최대 B명의 응시자를 감독할 수 있다. 추가로 필요한 경우 부감독관을 여러 명 배치할 수 있으며, 부감독관 한 명은 최대 C명의 응시자를 감독할 수 있다.모든 응시생을 감독하기 위해 필요한 최소한의 감독관 수를 계산하는 것이다.해결 방법: 수학적 계산을 통한 최적화이 문제는 각 시험장마다 필요한 감독관의 수를 계산하여 합산하면 된다. 중요한 점은 각 시험장마다 반드시 총감독관이 1명 있어야 한다는 것이다.구현 단계입력 받기시험장의 수 N과 각 시험장마다의 응시자 수 A_i를 입력받는다.총감독관이 감독할 수 있는 응시자 수 B와 부감독관이 감독할 수 있는 응시자 수 C를.. 2024. 10. 22. 백준 뱀 [3190] Python 코드 + 해설 문제 설명이 게임은 뱀이 사과를 먹으면서 길어지고, 벽이나 자기 몸에 부딪히면 게임이 끝나는 간단한 규칙을 가지고 있다.게임은 N x N 크기의 정사각형 보드에서 진행된다. 뱀은 처음에 보드의 맨 위 맨 좌측에 위치하며, 오른쪽을 향하고 있다. 몇몇 칸에는 사과가 놓여있다.뱀은 매 초마다 이동하며, 이동 규칙은 다음과 같다:뱀은 머리를 다음 칸으로 이동시킨다.이동한 칸에 사과가 있으면 사과를 먹고 꼬리는 그대로 있다 (몸길이가 늘어난다).이동한 칸에 사과가 없으면 꼬리를 줄여서 몸길이는 그대로이다.만약 벽이나 자기 자신과 부딪히면 게임이 끝난다.게임이 몇 초 만에 끝나는지 계산하는 것이 이 문제의 목표이다.해결 방법: 시뮬레이션을 사용한 구현이 문제는 시뮬레이션을 통해 해결할 수 있다. 매 초마다 뱀의 .. 2024. 10. 22. 백준 2048 (Easy) [12100] Python 코드 + 해설 문제 이해하기2048 게임은 4×4 크기의 보드에서 숫자 블록을 이동시키며 즐기는 게임이다. 하지만 이번 문제에서는 보드의 크기가 N×N (1 ≤ N ≤ 20)으로 주어지고, 최대 5번의 이동으로 만들 수 있는 가장 큰 블록의 값을 찾아야 한다.게임 규칙 정리상하좌우 네 방향으로 보드의 모든 블록을 한꺼번에 이동시킬 수 있다.같은 숫자를 가진 두 블록이 충돌하면 하나로 합쳐진다.한 번의 이동에서 이미 합쳐진 블록은 다시 합쳐질 수 없다.최대 5번 이동하여 가장 큰 블록의 값을 구해야 한다.해결 방법: DFS로 모든 경우의 수 탐색하기이 문제는 모든 가능한 이동 조합을 시도해보는 방법으로 해결할 수 있다. 최대 이동 횟수가 5번이므로, 가능한 이동의 수는 4^5 = 1024가지이다. 따라서 DFS(깊이 우.. 2024. 10. 22. 백준 구슬 탈출 2 [13460] Python 코드 + 해설 문제 설명구슬 탈출은 빨간 구슬을 구멍에 넣는 것이 목표인 게임이다. 직사각형 보드에 빨간 구슬과 파란 구슬이 각각 하나씩 놓여 있으며, 보드를 기울여 구슬들을 움직일 수 있다. 중요한 점은 파란 구슬은 구멍에 들어가면 안 되고, 빨간 구슬만 구멍에 빠져야 한다. 보드를 왼쪽, 오른쪽, 위, 아래로 기울일 수 있으며, 한 번 기울일 때마다 구슬들은 그 방향으로 모두 이동할 수 있을 만큼 이동한다. 두 구슬은 동시에 움직이며, 이동 중에 서로 겹칠 수 없다. 목표는 최소 횟수로 빨간 구슬을 구멍에 넣는 것이다. 단, 이동 횟수는 10번을 초과할 수 없다. 그렇다면 어떻게 이 문제를 해결할 수 있을까?해결 방법: BFS를 활용한 상태 탐색이 문제는 구슬들의 모든 가능한 상태를 탐색하여 최소 횟수로 빨간 구슬.. 2024. 10. 21. 이전 1 2 3 다음 728x90 반응형
