1. 풀이 (1). bfs로 탐색을 할 때 핵심은 한칸씩 이동할 때 마다 해당 부분을 큐에 넣어주는것. 즉 해당 점까지의 최단거리를 탐색과 동시에 찾는것이다. (2). 이 문제에서는 90도로 한번 방향을 전환하는 것 또한 한번의 이동으로 간주한다. 따라서 방향을 한번 이동한(왼쪽으로 90도, 오른쪽으로 90도) 후 큐에 넣어야 한다. (3). 한번에 최대 3칸까지 이동할 수 있다. 그리고 이러한 이동도 한번의 횟수로 치기 때문에, 각각을 큐에 넣어주어야 한다. (4). bfs 2차원 리스트에 차원을 하나 더 추가해서 (R,C)위치에서 turn 방향일때의 최솟값을 저장한다. 즉 (bfs[i][j][turn] : 시작점에서 에서 (i,j)점의 turn방향까지의 최솟값) 2. 소스코드 from collecti..

1. 풀이 (1) 답은 목적지까지 도달이 가능한지 안한지만 알면 된다. (2) 오직 편의점에서만 충전이된다. 즉 현재위치에서 편의점까지의 거리가 50*20(=1000) 맨하탄 거리 이내이면 이동이 가능하다. (3) 즉 현재위치와 1000맨하탄 거리 이내에 있는 편의점 사이에 (가중치가 일정한) 간선이 있는 그래프로 문제를 해석할수 있다. (4) 가중치가 일정한 그래프의 최소거리구하기 -> bfs ​ 2. 소스코드 from collections import deque def manhaten(a,b,c,d): return abs(a-c)+abs(b-d) T=int(input()) for t in range(T): ans = "sad" N=int(input()) homeX,homeY=map(int,input(..

1. 풀이 기본적인 bfs에 차원을 추가해서 응용되는 문제. 1). cL[i][j]는 시작점에서 i,j까지 갈 수 있는 최단거리가 저장된다. 2). bfs의 특성상 특정지점 (i,j)에 처음으로 방문한 순간이 최단거리가 된다. 즉 첫 방문에 최단거리임을 보장한다. 따라서 visited 리스트로 따로 방문여부를 관리할 필요가 없다 (방문했다면 해당자리 cL[i][j]에 원점에서 (i,j)까지의 거리가 적혀있을 것이고, 그것은 항상 최단거리이기 때문에) 3). 벽을 부수는횟수, 말 점프횟수가 제한되어있기 때문에 차원을 추가하여 해당 횟수를 관리한다. 2. 소스코드 (1) [백준]2206 벽부수고 이동하기 from collections import deque N,M=map(int,input().split())..

0 1 2 3 4 5 6 7 8 9 10 11 행렬에서 위와같이 번호(num)를 매기고 싶다면. (행) i=num//col (열) j=num%col ​ ​ ex) 6의 행렬? 1. num으로 행렬값? 6의 행은 col의 개수 4로 나눈 몫 == 1, 열은 col의 개수 4로 나눈 나머지 == 2. 따라서 (1,2) ​ 2 행렬로 num값? num=i*col개수+j

1. 문제 키를 비교하는 몇가지의 조건들이 주어졌을 때, 키 순서를 정확히 알수있는 학생이 몇명되는가? ​ 2. 해결 1~N학생이 있을 때 각 학생별로 1. 키가 작은쪽으로 탐색(bfs or dfs)한번, 2. 키가 큰쪽으로 탐색한번을 해서 1 + 2 = N-1이 되는지 확인하고, 되면 그 학생은 정확한 순위를 알 수 있다고 판단. ​ 3. 소스코드 #include #include #include #include using namespace std; vector to[501]; vector reversedTo[501]; int main() { int ans = 0; int N, M; cin >> N >> M; int a, b; for (int i = 0; i > a >> b..

S.W Expert. 6057그래프의 삼각형(D3) 이전코드(2000ms 초과) 이후코드(411ms) for t in range(int(input())): tri=0 N,M = tuple(map(int,input().split())) L=[[] for i in range(N-1)] pair=[] for m in range(M): a,b= list(map(int,input().split())) pair.append({a,b}) L[a-1].append(b) for n in range(N-2): for i in range(len(L[n])): for j in range(i+1,len(L[n])): if {L[n][i],L[n][j]} in pair: tri+=1 print(f"#{t+1} {tri}") fo..

1. 시간 queue 모듈과 deque모듈을 이용하여 풀었을 때 queue모듈은 시간초과가 났고 deque모듈은 통과되였다. 기본적으로 두 모듈 모두 알고리즘은 똑같다. 2. 소스코드 (1) queue(시간초과) queue로 while문을 돌리기 위해선 매 반복마다 while(not q.empty()) 연산을 수행해야 하는데, 이것때문에 시간이 오래 걸린것으로 보인다 import queue N,M=map(int,input().split()) L=[] for i in range(N): L.append(list(map(int,list(input())))) q=queue.Queue() q.put((0,0,0)) cL=[[[0,0] for i in range(M)] for j in range(N)] cL[0][..

1. 풀이 bfs로 풀어야 한다 Q. 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 2. 소스코드 import queue N,K=map(int,input().split()) q=queue.Queue() time=0 q.put(N) visitedL=[0]*100001 visit..

N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 1. dfs from collections import deque from copy import deepcopy N,M=map(int,input().split..

Q. 각각의 시계추의 무게가 주어질 때 ( ex) weight=[3, 1, 6, 2, 7, 30, 1] ) 시계추로 잴 수 없는 가장 작은 양의 정수는? 1. 풀이 오름차순으로 정렬된 weight를 앞에서 누적하여 더해가며, 다음으로 큰 숫자보다 그 합이 작을때 stop => 더이상 더할것이 없으므로 2. 소스코드 def solution(weight): weight.sort() length=len(weight) s=1 for i in range(length): if s

1. 풀이 (1) 현재 가지고 있는 기름으로 방문가능한 모든 주유소 중에 가장 기름을 많이 넣을 수 있는 주유소를 후보에 추가한다. (이때 후보주유소는 힙으로 관리한다. 게속 추가하고 매회 최댓값을 추출해야 하기 때문) (2) 후보(heap)에서 최댓값을 추출한다. (이때 방문횟수를 +1) * 만약 방문할 주유소가 없으면 답은 -1 2. 소스코드 import heapq import sys from collections import deque N=int(input()) point=[] for i in range(N): a,b=map(int,sys.stdin.readline().rstrip().split()) point.append([a,b]) L,P=map(int,input().split()) point...

1. 풀이 dp[i][j] : i에서 j문자열까지 만들 수 있는 길이 중 최대 dp[i][j]를 구하기 위해선 아래 두가지를 고려해주면 된다. ​ (1) (A[i]==a and A[j]==t) or (A[i]==g and A[j]==c) 인경우 dp[i+1][j-1]+2 => 양끝이 조건에 만족하면 KOI유전자 (2) dp[i][j]=max(dp[i][j-s]+dp[i+j+1-s][j] (k: 1~j-i)) => () + ()가 가능(각조합에서 최댓값 찾기) 2. 소스코드 A=input() size=len(A) dp=[[0 for j in range(size)] for i in range(size)] for j in range(1,size): for k in range(size-j): dp[k][j + ..