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

1. 풀이 이진탐색의 기본구조는 아래와 같다. while(left

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) L[r][c]==0인 숫자를 찾아서 1~9까지 중 넣을 수 있는 숫자를 넣는다 (2) num을 한칸 더가서 dfs를 돈다 (3) 다돌고 난 후엔 해당 위치 L[r][c]를 다시 0으로 돌려놓는다 ​ 2.소스코드 (1) sys.exit()으로 종료 import sys L=[] for i in range(9): L.append(list(map(int,input().split()))) #행, 열, 구역 검사 def cheak(L,r,c,num): #행검사 if num in L[r]: return False #열검사 for i in range(9): if L[i][c]==num: return False #영역검사 dR = [-1, -1, -1, 0, 0, 0, 1, 1, 1] dC = [-1, ..

1. 풀이 (1) 1이나오는 지점에서 가능한 색종이를 종류별(1~5)로 모두 붙여본다 (2) 크기가 현재 ans보다 크면 백트래킹 ​ 2. 소스코드 (1) 두번의 DEEPCOPY, 시간초과 안전한 코드를 위해 stack이 시작할때 리스트들을 copy해주었다. 하지만 스택에 넣을 때 copy를 해준 후 넣기 때문에 L에는 영향이 없다. 따라서 스택이 시작할 때 다시 copy를 해주지 않아도 된다. from collections import deque from copy import deepcopy L=[] for i in range(10): L.append(list(map(int,input().split()))) stack=deque([[[0 for i in range(5)],L,0]]) ans=26 def..

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

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