![]()
대표적인 섬 찾기 bfs 문제. MAP 자체에 visited를 2 표시해서 풀이함. 0으로 표시할걸.. 생각이 짧았다 문제 https://www.acmicpc.net/problem/1012 풀이 import sys import collections input = sys.stdin.readline move = [(-1,0),(0,1),(1,0),(0,-1)] def bfs(i,j,MAP): q = collections.deque() q.append((i,j)) MAP[i][j] = 2 #visited while q: x,y = q.popleft() for tx,ty in move: nx = x + tx ny = y + ty if 0
![]()
bfs로 풀 수 있는 문제로, 기존 bfs가 보통 2차원 MAP을 기준으로 하는것을 1차원으로 축소한 문제 기존 bfs의 탐색방향이 북,동,남,서 였다면 이 문제는 U,D 로 풀이 문제 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 import sys input = sys.stdin.readline import collections F, S, G, U, D = map(int,input().split()) def bfs(): q = collection..
![]()
ex) 4의 경우 3에서 가능한 모든 경우의 수에 +1을 더하는 경우가 더해짐 1+1+1 +1, 2+1 +1, ... 이런식.. 근데 1, 2, 3을 더할 수 있으니 dp[i-1], dp[i-2], dp[i-3]을 모두 더해주면 모든 경우의 수를 고려하게 되는 것 문제 https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 import sys input = sys.stdin.readline T = int(input().strip()) dp = [1, 2, 4] def fill_dp(dp, n): ..
![]()
기본 동작은 boarding 함수를 통해 수행하고 배의 현재 위치와 다음으로 태울 (min_time_arrv) 손님의 위치를 고려하여 main flow 수행 문제 https://www.acmicpc.net/problem/2065 2065번: 나룻배 강을 사이에 두고 위치한 두 정박장 사이를 한 대의 나룻배가 오가고 있다. 두 정박장은 강을 기준으로 왼쪽(left), 오른쪽(right)으로 구분한다. 제일 처음에는 나룻배가 왼쪽 정박장에 위치해 있 www.acmicpc.net 코드 import sys input = sys.stdin.readline from collections import deque M, t, N = map(int,input().split()) left = deque() right = d..
