분류 전체보기

BFS) 4991.로봇 청소기

solution 중복되는 탐색 루트 제거. 시간 복잡도 10! x 10 = 36288000 = 약 3천만 문제의 관건은 중복되는 탐색 루트를 줄이는 것이다. 문제 유형은 브루트 포스 + BFS인데, 더러운 곳의 개수가 10개 미만이고, 격자 칸의 최대 크기는 20*20이므로, 만일 10개의 더러운 칸으로 만드는 순열의 조합 각각의 경우 BFS 탐색을 한다고 하면, 최악의 경우 시간 복잡도 10! x 20*20 >= 12억이다. 따라서 중복되는 탐색 루트를 제거할 필요가 있다. 시작점에서부터 더러운 곳을 차례로 방문하는 경우의 최단 거리는 중복된다. 가령, 더러운 곳이 3 곳이고, 그 번호를 1,2,3으로 하며, 더러운 곳과 시작점을 모두 정점이라고 한다면, 모든 순열의 경우의 수는 시작점 -> 1 -> ..

BFS) 5014.스타트링크

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 from collections import deque import sys f,s,g,u,d=map(int,input().split()) q=deque() q.append((s,0)) check=[False]*(f+1) check[s]=True while q: now,cnt=q.popleft() if now==g: print(cnt) sys.exit(0) for next in [now+u,now-d]: if 1

BFS) 14395. 4연산

https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net # solution # 정점 = 가능한 수의 개수, 간선 = 4개 연산, 가중치 = 연산 1번 이므로, BFS로 풀이 가능하다. # 이때, 정점의 개수는 10억(1e9)가 아니다. # 왜냐하면 4개 연산 중 *,+를 제외한 /,-는 1,0의 결과를 내기 때문에, 결국 가능한 경우의 수는 x^a*2^b의 형태를 띠게 된다. # 또한 이것의 크기는 사실상 10억을 넘지 않는다. # 그 이유는 ..

BFS) 10026.적록색약

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net from collections import deque n=int(input()) a=[list(list(input())) for _ in range(n)] dx=[-1,1,0,0] dy=[0,0,-1,1] def can(blind,a,b): if a==b: return True if blind: if (a=='R' and b=='G') or (b=='R' and a=='G'): return..

BFS) 1963. 소수 경로

https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net # solution 1. # 모든 경우의 수를 전부 찾는 완전탐색이면서 BFS를 사용한 문제이다. # # 우선 네 자리 수인 9999까지의 모든 수를 완전탐색을 통해서 소수인지 판별을 한다. # # 그 다음은 각 자리수마다 숫자(0 ~ 9)를 바꾸어 가며 소수인 수는 큐에 넣어서 또 다시 자릿수를 바꾸어 가며 바꾸어야 하는 숫자가 나올 때 판별한다. # # 이 때 다음과 같은 조건을 생각해야 한다. # #..

BFS) 6087.레이저 통신

https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net # solution. # BFS의 가중치를 직선의 개수로 설정한다. # 즉, 시작점부터 해당점까지 도달하기 위해 필요한 직선의 개수를 dist 배열에 업데이트한다. # 여기서 필요한 직선의 개수 -1 이 필요한 거울 개수의 최솟값이므로 dist 배열의 타겟 지점의 값에서 -1을 해주면 답을 구할 수 있다. # 가중치가 다르므로, BFS 탐색을 할 때, 각 방향에서 벽을 만나거나 탐색 범위..