📌문제 출처 백준 단계별 문제풀이 - 그래프와 순회 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net ❓ 문제 ❗ 풀이 bfs 응용(3차원 방문 확인) 📗 풀이 코드 import sys from collections import deque input = sys.stdin.readline def bfs(): stack = deque([[1,0,0,0]]) while stack : cnt,y,x,crashed = stack...
📌문제 출처 백준 단계별 문제풀이 - 그래프와 순회 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 ❓ 문제 ❗ 풀이 heap 자료구조 활용 bfs 📗 풀이 코드 import sys from heapq import heappush, heappop input = sys.stdin.readline def bfs(): heap = [[0,1]] # 0회 이동, 출발점은 1번 while heap : cnt..
📌문제 출처 백준 단계별 문제풀이 - 그래프와 순회 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net ❓ 문제 ❗ 풀이 3차원 bfs 활용 📗 풀이 코드 import sys from collections import deque input = sys.stdin.readline def bfs() : # 0일자부터 토마토 익히기 시작 global not_good cur_day = 0 # 현재 날짜 while stack : z,y..
📌문제 출처 솔브닷 3+ 클래스 단계 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net ❓ 문제 ❗ 풀이 bfs 활용 풀이 📗 풀이 코드 import sys from collections import deque, defaultdict input = sys.stdin.readline def bfs(i): stack = deque([i]) while stack: for j in dic[stack.popleft()]: if not visited[j] : #..
📌문제 출처 솔브닷 3+ 클래스 단계 https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net ❓ 문제 ❗ 풀이 set 자료구조 활용 📗 풀이 코드 import sys input = sys.stdin.readline n,m = map(int,input().split()) no_listen = set([input().strip() for _ in range(n)]) no_see = set([input().strip() for _ in range(m)])..
📌문제 출처 솔브닷 3+ 클래스 단계 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net ❓ 문제 ❗ 풀이 dp 활용 📗 풀이 코드 import sys input = sys.stdin.readline dp = {0:1,1:1,2:2} for i in range(3,12): dp[i]=dp[i-3]+dp[i-2]+dp[i-1] for _ in range(int(input())): print(dp[int(input())]) 📗 코드 해설 해당 문제는 하나씩 수열을 늘려가다보면 점화식은 금방 찾을 수 있다. dp[i] = dp[i-3] + dp[i-2..
📌문제 출처 솔브닷 클래스 3+ 단계 https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net ❓ 문제 ❗ 풀이 hash 자료구조 활용 📗 풀이 코드 import sys input = sys.stdin.readline n,m = list(map(int,input().split())) dic = {} for i in range(1,n+1) : name = input().strip() dic[str(i)] = name dic[n..
📌문제 출처 솔브닷 클래스 3+ 단계 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net ❓ 문제 ❗ 풀이 bfs 활용 📗 풀이 코드 import sys from collections import defaultdict, deque input = sys.stdin.readline def bfs(n): stack = deque([[n,0]]) cnt = 0 while stack: i,cnt = stack.popleft() if i==1: return cnt cnt += 1 if (not i%3)and (not visited[i//3]): stack.append([i..
