안녕

0. 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 풀이 방법 이중 for loop를 사용하여, 모든 맵을 훑는다. 이때 무인도인데, 방문한 적이 없다면 BFS를 통해 연결된 무인도를 찾고, 먹을 수 있는 모든 음식을 찾는다. 이를 append 하고, 반환은 정렬해서 반환하도록 한다. 2. 코드 from collections import deque def solution(maps): def bfs(y, x): food = i..

0. 문제 링크 https://www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 ≤ N ≤ 50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문 www.acmicpc.net 1. 풀이 방법 BFS + 구현으로 문제를 풀었는데, 방문 처리가 가장 중요한 문제이다. 방문 처리와 더불어서 어떤 조건일 때 방문을 허락할지도 잘 체크해야 한다. 방문 처리는 비트 2개를 사용해서 해결하였다. 0은 미방문, 1은 가로가 방문, 2는 세로가 방문, 3은 가로세로 모두 방문 어떤 조건일 때 방문을 허락할지는 구현 문제이므로 이건 생략하겠다. 2..

0. 문제 링크 https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 1. 풀이 방법 다들 적군이 내려온다고 생각하는데, 나는 그냥 궁수가 올라가는 방식을 사용했다. 궁수가 적을 찾는 과정은 (우선순위에 따라)BFS로 해결하였고, 적을 찾으면 적의 위치를 반환하였다. 여러 궁수가 같은 적을 찾는 경우를 고려하여 적의 위치를 set으로 해결하였다. 궁수의 자리는 조합을 이용하여 BF하게 해결하였다. 2. 코드 import sys from itertools imp..

0. 문제 링크 https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 1. 풀이 방법 BFS 문제이고, 방문 표시를 잘해야 한다. 특정 키를 가지고 있음을 비트로 표현하는데, 방문 표시는 특정 키들을 가지고 이 칸에 방문한 적이 있느냐? 가 되겠다. 따라서 키는 총 6개이므로, 000 000 ~ 111 111의 경우의 수를 가질 수 있다. 따라서 총 64개의 경우의 수가 존재한다. 이제부터 모든 칸을 돌면서 특정 비트(..

0. 문제 링크 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 1. 풀이 방법 육지를 찾으면 BFS를 통해 육지를 모두 같은 그룹 번호로 지정한다. BFS를 하면서 육지의 가장자리를 찾게 된다면 가장자리 BFS에 저장한다. 모든 육지를 찾으면 위에서 저장한 가장자리 BFS로 다른 육지를 탐색한다. 이때 나와 같은 그룹 번호를 찾는다면 패스하고, 다른 육지 번호일 때만 최단 거리를 업데이트한다. 만약 바다에서 BFS 하던 도중 기존의 최단 거리보다 ..

0. 문제 링크 https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 1. 풀이 방법 완전 탐색 비슷하게 풀었다. 참고로 BFS이다. 다만 최대 10억 개를 탐색해야 하는데, 이렇게 하면 무조건 시간초과가 난다. 최대 1,000,000의 길이이지만, 각 위치의 숫자는 0~9이다. 따라서 무조건 중복이 발생한다. 그러므로 중복을 잘 체크한다면 빠르게 풀 수 있다. BFS를 할 때는 실제로 자리를 바꿔줘서 해결하면 된다. *참고로 string끼리 대소비교 가능하다. 2. 코드 import sys from collection..

0. 문제 링크 https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 1. 풀이 방법 문제를 보자마자 BFS로 풀려고 했다. 여기서 키포인트는 비어있는 칸에 방문했는데, 근처에 쓰레기가 있다면 해당 비어있는 칸을 다른 어떤 값으로 변경해줘야 한다. 아 그리고 문제를 잘 읽어야 한다. 처음에 문제 잘못 읽어서 조금 고생했음 풀이 방법은 비교적 쉽다. 비슷한 류의 문제를 풀어서 그런가 쉽게 느껴졌음 왜냐면 최적의 조건이 딱 ..

0. 문제 링크 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 1. 풀이 방법 음... 해당 문제는 매우 쉬웠다. 그냥 BFS를 하면 풀리는 문제다. 이때 익혀야 하는 토마토의 개수를 미리 세서, 그 개수만큼 되면 끝내게 했다. 만약 해당 갯수만큼 모두 채우지 못했는데, BFS가 끝나버리면 이는 모두 채우지 못하는 것이므로 -1을 반환하였다. 2. 코드 from collections import deque import ..

0. 문제 링크 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 1. 풀이 방법 우선 빙산의 녹음을 구현한 함수인 melt()와 그룹화하는 함수인 group() 함수를 구현했다. 그리고 빙산 근처에 바다의 개수를 세는 adj도 따로 만들어서, 빙산 근처에 몇 개의 바다가 있는지 셌다. melt() 함수를 사용하고, 다시 인접한 바다의 개수를 셌다. 만약 특정 빙산이 모두 녹았다면 해당 빙산은 adj 딕셔너리에서 pop 하였다. group(..

0. 문제 링크 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 1. 풀이 방법 2023.02.21 - [Computer Science/알고리즘] - [백준 - Python] 17141 - 연구소 2 공간을 다시 정의했다. 어차피 활성 바이러스 된다해도, 기존에 BFS에서 돌던게 있으니까 상관 없고, 결과적으로 진짜 비어있는 공간만 채우면 된다. 그래서 해당 글의 코드를 그대로 가져와서 그냥 공간만 다시 정의하고 제출했더니 성공; 2. 코드 import..