https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net # 꽤 까다로운 BFS 문제이다. # 이 문제를 푸는데 있어서 주의할 점은 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없으므로 물을 먼저 흘려보낸 뒤 고슴도치를 이동시켜야 한다는 것이다. # dist_beaver는 고슴도치가 이동하는데 걸리는 시간, dist_water는 물이 차는데 걸리는 시간 두 가지 배열로 상태를 나타내고 비교했다. # bfs_water함수를 통해 먼저 물을 흘려보낸 뒤, ..
https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net # BFS 문제이다. # 1번 후보부터 N번 후보까지 각각 bfs함수를 실행해 dist값을 갱신해준다. (dist값 = 현재 후보와의 거리 = 문제에서 요구하는 '점수') # dist값의 최대가 현재 후보의 점수이다. 따라서 점수가 가장 작은 사람이 회장후보이므로 chairman 배열에 회장후보들을 넣어준다. 마지막에 점수와, 후보 수, 후보들을 출력해주면 끝 import sys from coll..
https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net # BFS문제이다. # 100번 칸에 도착하기 위해 주사위를 굴려야하는 횟수의 최솟값을 구하는 문제 1. N개의 사다리의 (시작점, 끝점)과 M개의 뱀의 (시작점, 끝점)을 각각 dictionary에 넣어준다. 2. bfs()를 수행하는데, 처음에 1번칸에서 시작하므로 q에 1을 넣고 시작한다. 2-1. 현재 x번째 칸에서 k값을 더한 x+k가 다음칸..
https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr BFS문제이다. from collections import deque def solution(n, computers): cnt = 0 visited = [False] * (n+1) graph = [[] for _ in range(n)] q = deque() # 연결되어 있는 컴퓨터 graph에 저장 for i in range(n): for j in rang..
https://programmers.co.kr/learn/courses/30/lessons/43165?language=python3 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 무난한 DFS/BFS 문제이다. def solution(numbers, target): global answer answer = 0 cnt = 0 dir = [-1, 1] # 숫자를 더하거나 빼거나 둘 중 하나이므로 [-1, 1] 선언 def dfs(cnt, k): global ..
www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 전형적인 그래프 탐색문제이다. 1. m에 마당을 입력받고 마당칸 만큼 visited배열을 만들어주고 False를 넣어준다. 2. bfs함수: sheep, wolf = 0, 0으로 설정하고 bfs를 돌려준다. q에서 x, y원소를 뽑고 m[x][y]가 o라면 sheep 1증가, v라면 wolf를 1증가시키고 m[x][y]를 #으로 변경 3. 상하좌우 방향을 탐색하며 좌표 밖을 벗어나지 않고 m[nx]..
모르는 사이에 조금씩 조금씩..
