조준장 개발자 생존기

문제 11123번: 양 한마리... 양 두마리... 얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지. 그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!" www.acmicpc.net 알고리즘 - dfs 탐색을 통해 문제를 수행한다. - 케이스만큼 반복하여 양의 무리를 출력한다. 코드 import sys sys.setrecursionlimit(10 ** 6) # 재귀 허용 깊이를 수동으로 늘려주는 코드 # dfs 탐색 def dfs(x, y): if x = h or y = w: return False # 탐색하지 않았다면 탐색 if graph[x][y] == "#": # 탐색 확인 graph[x][y] = "." # 양..

문제 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 총 6가지의 경우의 수를 가지고 탐색한다. - 물의 총량이 고정이기 때문에 a, b 두 물통만 체크하여 c 물통의 물의 양을 계산한다. - a 물통이 비어있는 경우에 c 물통에 남아있는 물의 양을 저장한다. 코드 import sys from collections import deque # a 물통과 b 물통의 경우의 수 저장 def pour(x, y): if not visited[x]..

문제 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하이고, D는 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주 www.acmicpc.net 알고리즘 - bfs 탐색으로 문제를 수행한다. - 0부터 고속도로의 길이까지 반복하여 최단 거리를 구한다. - 지름길로 간 거리와 고속도로로 간 거리를 비교하여 최단 거리를 입력한다. - 지름길을 반복하여 최단 거리를 찾는다. 코드 import sys n, d = map(int, sys.stdin.readline().split()) graph = [list(map(int, input().split())) for _ in range(n)] dis ..

문제 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..