1. 풀이 (1) 모든 가능한 궁수의 위치에 대한 경우의 수를 구한다. (2) 하나의 경우의 수에 대해서 아래를 수행한다 - 궁수공격 - 적이동 ​ * "(1) 궁수의 공격"에서 여러 궁수가 조건에만 만족한다면 같은 적을 동시에 쏠 수 있다는것을 주의한다. * 또한 "(1) 궁수의 공격" 은 [1. 극한의 구현]을 하거나 짧은거리부터 공격을 하고, 거리가 같으면 왼쪽부터 공격하므로 [2. bfs를이용]할 수 있다. ​ [1. 극한의 구현] from copy import deepcopy from itertools import combinations N,M,D=map(int,input().split()) L=[] for i in range(N): L.append(list(map(int,input().spli..

1.풀이 (1) 플로이드와샬을 이용하여 연결되어있는지를 확인한다. (2) bfs를 통해 연결되어있는 컴포넌트에서 경찰서 건설비용이 가장 작은곳에 경찰서를 짓는다. ​ 위의 방법으로 어거지로 풀었지만 아래와 같이 최적화하여 푸는 방법을 찾아본다. *최적화 풀이 (1) dfs(강연결요소)를 통한 풀이 (2) 유니온-파인드를 이용. ​ 2. 소스코드 (플로이드와샬, bfs) INF=9876543210 N=int(input()) cost=list(map(int,input().split())) L=[] for i in range(N): L.append(list(map(int,list(input())))) def floid(): #초기값 설정 for i in range(N): for j in range(N): if..

1. 최단거리 2. 최소스패닝 트리(MST)

1.풀이 [백준]1035 조각움직이기 (https://sosoeasy.tistory.com/39) 와 비슷한 문제이다. (1) 모든 경우의 수를 조합으로 구한다 (2) (1)에서 구한 경우가 임도연파(Y)가 4명이상인지 확인한다. (3) 4명이상이면 bfs를 통해서 연결되어있는지 확인한다. - 소스코드1 : dfs를 이용하여 연결여부 확인 - 소스코드2 : bfs를 이용하여 연결여부 확인 -> 내생각엔 이게 더 쉽다. * 이런류의 문제를 백트래킹으로 생각하면 조건 처리가 힘들어지는 경우가 많다. 완전탐색으로 보이는 문제는 깔끔하게 순열, 조합으로 풀 수 없을까 고민하는 자세가 필요하다. 2. 소스코드 (1) 소스코드1 (dfs를 이용) from itertools import combinations dR=..

구글링 해보니 4차원 dp를 이용해서 푼사람들이 많았다. 나는 안똑똑해서 dfs를 이용하여 풀었다. 1. 풀이 [백준]4991 로봇청소기(https://sosoeasy.tistory.com/24) 문제와 유사하다. 아래의 순서를 따른다. (1) 현재위치에서 남아있는 모든 C까지의 거리를 bfs를 통해서 구한다. (2) (1)에서 구한 모든 경우에 대해서 해당 점을 시작위치로 하여 dfs를 한다. 2. 소스코드 INF=9876543210 from collections import deque dR=(-1,0,1,0) dC=(0,-1,0,1) N,M=map(int,input().split()) L=[] for i in range(N): L.append(list(input())) def bfs(case,q,vi..

1. 풀이 (1) bfs를 돌리려다 8자리 숫자를 visited처리해주기 위해서 100000000개의 리스트를 만들었다. 하지만 메모리초과. (4*100000000byte=390625KB=381MB) (2) 이후 수학&그리디로 풀려고 시도했지만 규칙 못찾음 (3) visited를 set으로 관리하면 됨. ​ * visited를 무조건(0 or 1) 값을 갖는 리스트로만 생각하지말고 set or dictionary도 생각해줄것! ​ 2. 소스코드 from collections import deque N,K=map(int,input().split()) L=list(input().split()) visitedS=set("".join(L)) q=deque([["".join(L),0]]) ans=-1 while(..

1. 풀이 일반적인 많이풀던 (grid) bfs문제와 비슷한데 index처리를 너무못해서 너무 오래 걸렸다. 처음에는 visited를 고려해주지 않아서 메모리초과(시간초과)가 났다 ((1)메모리초과, visited사용x) 모든 경우의 수를 다 따져주어야 한다고 생각했지만, a=acs , b=acbs , c=acacbss 일때 아래의 두 경우는 같은 경우이기 때문에 visited로 관리해줘서 한가지 경우만 탐색해 주어야 시간을 줄일 수 있다. ((2)통과) a c s 1 2 a c b s 3 4 a c s 3 4 a c b s 1 2 이후 vistied를 사용해서 큐를 구성할 때 인덱스 에러가 많이 났다. (1) 다음 방문지를 기준으로 q에 넣을 수 있는지 검사하고(aIndx+1

1.풀이 처음에 생각한 방법은 가장 가까운 먼지부터 먼저 방문하고, 그러한 먼지가 여러개일 경우를 dfs로 탐색해주는 그리디한 방법을 생각했다. 하지만 이는 다다음 먼지의 위치에 따라 더 긴 경로가 될 수 있다. 아래의 경우가 그 반례이다. * . . . . . . . . . . . . . * . . . . . . o . . . . . . . . . . . . . * 그리디하게 접근한다면 시작점에서 왼쪽위 먼지로 가야하지만, 그러면 총 이동거리는 16이된다. 하지만 제일 오른쪽 아래에 있는 먼지부터 먼저 접근하면 총 이동거리는 14가 된다. 따라서 모든 경우를 탐색해 주어야 한다. (근데 2차원 평면이아닌, 1차원 직선에선 그리디하게 접근해도 되는거 같음..) ​ 올바른 접근방법은 (1) 시작점에서 모든..

1. 풀이 풀이 방법은 아래와 같다. (1) 백조끼리 만날 수 있는지 확인 (2) 물에 닿는 빙판을 물로 녹이기 (3) 시간+=1 처음에 했던 단순한 풀이는 (1)을 항상 1번백조에서 2번백조로 bfs를 통해서 확인하고, (2)를 처음부터 끝까지 2중포문으로 돌면서 상하좌우에 물이 닿아있는것을 체크해준 뒤, 반복문이 끝나고 한꺼번에 녹여주는 방법을 썼다. 하지만 이것은 시간초과를 발생시켰다. 해결방법은 이전까지 확인해준 영역을 저장해 두었다가 다음 반복에서 생략해 주는 것이다. 즉 (1)에서는 1번백조에서 bfs를 통해 뻗어 나갈 수 있는 최대한으로 뻗어나가서 테두리를 저장해두고 해당 테두리만 q에 넣어서 다음반복에서 bfs를 돈다. 방문했던 곳은 다시 방문하지 않기위해 swanVisited리스트로 이를..

1. 풀이 일반적인 bfs를 사용하면 된다. 이때 주의할 점 세가지가 있다. (1) 방문된것을 확인해주는 visited 리스트로 중복방문 관리하기. -> visited로 중복방문을 관리해주지 않으면 방문한곳이 다시 방문되어 시간이 지수배로 증가한다. (2) 문자열 처리보다 숫자처리가 훨씬 빠르다. -> 몰랐어서 그냥 문자로 했다가 시간초과. (3) python으론 안된다. pypy로 돌릴것. ​ 2. 소스코드 (1) visited방문 처리x, 문자열로 순서처리, 시간초과 from collections import deque import sys d=["D","S","L","R"] def do(num,order): if order=="D": return str((int(num)*2)%10000) elif o..

1. 풀이 열쇠를 하나 획득하면, 이전에는 못갔던 길을 다시 가는것이 가능해질 수도 있다. 따라서 5개의 열쇠(a,b,c,d,e,f)를 갖는 경우의 수를 각각다 다르게 생각해주어야 한다. (1) 비트마스크 이때 경우의 수를 비트마스크로 처리해준다 => (a,b,c,d,e,f) 열쇠를 각각 갖고있으면 1, 아니면 0으로 나타내 줄 수 있는 2진수를 고려해 준다. ex) 모두 갖고있음 -> 111111 a,b,c,만 갖고있음 -> 111000 a,f만 갖고있음 -> 100001 모두 안갖고있음-> 000000 (2) bfs 열쇠를 하나 찾으면 지금까지 찾아진 열쇠에 해당하는 층으로 이동하여 (마치 벽부수고 이동하기처럼) 새로운 2차원 visited 리스트에서 탐색을 시작한다. (새로운 열쇠를 찾으면 이전에 ..

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())..

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

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