코딩 테스트/백준 강의 연습편
BFS) 2234.성곽
https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net from collections import deque # 서, 북, 동, 남. # 비트마스크로 벽 존재 여부를 체크해야 하므로, 위의 순서대로 0,1,2,3 으로 for문을 돌게 하여, # 2^0=1, 2^1=2, 2^2=4, 2^3=8 값이 포함되어 있는지 & 연산으로 검사한다. dx=[0,-1,0,1] dy=[-1,0,1,0] m,n=map(int,input().split()) a=[li..
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)를 바꾸어 가며 소수인 수는 큐에 넣어서 또 다시 자릿수를 바꾸어 가며 바꾸어야 하는 숫자가 나올 때 판별한다. # # 이 때 다음과 같은 조건을 생각해야 한다. # #..