조준장 개발자 생존기

문제 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 상어의 위치를 확인하고 상어의 위치부터 bfs 탐색을 수행한다. - bfs 탐색을 하면서 탐색하기까지 걸린 이동 횟수를 체크한다. - 이동 횟수의 최댓값에서 처음 시작 값을 빼고 출력한다. 코드 import sys from collections import deque # bfs 탐색 def bfs(): # 상/하/좌/우/대각선 dx = [1, -1, 0, 0, 1, -1, 1,..

문제 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 알고리즘 - dfs 탐색을 통해 문제를 수행한다. - 재귀 허용 깊이를 늘리지 않으면 런타임 에러가 나올 수 있다. [baekjoon] 백준 16956번(파이썬): 늑대와 양 문제 16956번: 늑대와 양 크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 fre2-dom.tistory.com - 위 문제와 비슷한 내용이지만..

문제 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net 알고리즘 - python 3으로 시간초과가 나와서 pypy3으로 해결 - bfs 탐색을 통해 문제를 수행 - 1번 노드부터 리프 노드까지 이동 횟수를 구하고 짝수이면 Yes를, 홀수이면 No를 출력 코드 import sys from collections import deque # pypy3으로 해결 # bfs 탐색 def bfs(x): queue = deque([x]) cnt = 0 # 큐가 없을 때까지 반복 while queue: target = queue..

문제 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 바이러스의 번호와 x좌표, y좌표, 시간을 리스트에 넣고 오름차순으로 정렬하여 큐에 넣는다. - 큐에 넣은 리스트를 하나씩 탐색하여 주위에 있는 바이러스가 존재하지 않는 칸에 증식한다. - 측정 시간과 현재 시간이 같으면 종료하여 특정 위치에 존재하는 바이러스의 번호를 출력한다. 코드 import sys from collections import deque # bfs 탐색 d..

문제 14716번: 현수막 혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라. www.acmicpc.net 알고리즘 - dfs 탐색을 통해 문제를 수행한다. - 그래프에서 1인 경우를 탐색한다. - 상/하/좌/우/대각선을 재귀적으로 탐색한다. 코드 import sys sys.setrecursionlimit(10 ** 6) # 재귀 허용 깊이를 수동으로 늘려주는 코드 # dfs 탐색 def dfs(x, y): if x = m or y = n: return False # 탐색하지 않았다면 탐색 if graph[x][y] == 1: # 탐색 확인 graph[x][y] = 0 # 상/하/좌/우/대각선을 재귀적으로 탐색 dfs(x + 1, y) # 오른쪽 dfs(x + 1,..

문제 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 6가지 이동 방법을 정의하고 반복문을 통해 현재 위치에서 6가지 방법으로 이동한다. - 범위 내에 있고 탐색하지 않았다면 이동후 좌표를 탐색한다. - 탐색한 좌표까지 걸린 이동 횟수를 초기화한다. - 목표 좌표까지 이동한 횟수에서 처음 시작 좌표에서 카운트한 값을 빼고 출력한다. 코드 import sys from collecti..

문제 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 보드판을 표현하는데 사다리와 뱀을 통해 이동하는 칸은 이동 후 좌표로 표시한다. - 주사위 눈만큼 반복하여 보드판을 이동한다. - 100칸이 넘으면 턴을 넘긴다. - 탐색하지 않은 칸이라면 탐색하고 100번째까지 칸까지 탐색했다면 리턴한다. - 100번째 칸까지 가기 위해 던진 주사위 횟수에서 1번째 칸에서 던진 주사위 횟수를 뺀 값을 출력한다. 코드 impo..

문제 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 알고리즘 - 매 단계마다 함수를 만들어 문제에서 원하는 모션을 수행한다. - 단계마다 시간초를 -1을 해주면서 시간 초가 다 지났을 때, 그래프 모양을 출력한다. 코드 import sys from collections import deque # 1단계 def loc_bomb(): for i in range(r): for j in range(c): if graph[i][j] == 'O': bomb.append((i, j)) # 3단계 def full_bomb(): for i i..

문제 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - if문을 통해 각 조건에 맞으면 큐에 추가한다. - 리스트의 원소가 1이면 리스트를 리턴받는다. 코드 import sys from collections import deque # bfs 탐색 def bfs(v): queue = deque([[v]]) while queue: # 큐 리스트에서 제일 작은 리스트부터 확인 target = queue.popleft() # 제일 작은 리스트에서 제일 작은 원소부터 확인 temp = target[0] # 원소가 1이면 그 리스트를 리턴 if temp == 1: return..

문제 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 토마토의 위치를 미리 저장해서 bfs 탐색을 한다. - 탐색이 모두 끝나고도 익지 않은 토마토가 있으면 -1을 출력한다. 밑에 문제를 풀고 이 문제를 풀면 좋을 듯하다. [baekjoon] 백준 7576번(파이썬): 토마토 문제 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단,..