ps/bfs & dfs 검색 결과

해당 글 33건

[bfs] [연결 요소] 바이러스 14502 (재)

문제 해설 및 주의사항 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다. 풀이 1. 문제의 구분 - 벽을 3개 세우는 것 (브루트 포스) 시간 복잡도 : (NM)^3 - 바이러스가 퍼질 수 없는 영역의 크기 구하기 (연결 요소의 개수) 바이러스가 있는 곳을 기준으로, 바이러스가 퍼질 영역을 dfs 혹은 bfs 로 구한 뒤, 여집합을 구하면 된다. 시간 복잡도 : (NM) 그러므로, 최대 경우의 수는 (8 ..
ps/bfs & dfs 2021. 10. 23. 19:46

[bfs][최단거리][역추적] DSLR 9019 ○

문제 해설 및 주의사항 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자) D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다. S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다. L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다. R: R 은 n의..
ps/bfs & dfs 2021. 10. 23. 15:57

[최단거리] 데스 나이트 16948

문제 해설 및 주의사항 1. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 2. 데스 나이트는 체스판 밖으로 벗어날 수 없다 3. 크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다. 풀이 1. 왜 bfs 인가? a. 최소 이동 횟수를 구한다. b. 한 번 이동 시, 한 번의 이동 횟수가 올라간다. 즉, 가중치가 1이다. c. 도착점, 시작점 존재 d. 최악의 경우 O(N^2) 인데, N 의 최대가 200이므로 충분하다..
ps/bfs & dfs 2021. 10. 23. 15:31

[bfs][최단거리] 뱀과 사다리 게임 16928

문제 해설 및 주의사항 1. 게임은 크기가 10×10이고, 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다. 보드판에는 1부터 100까지 수가 하나씩 순서대로 적혀져 있다. 2. 도착한 칸이 사다리면, 사다리를 타고 위로 올라간다. 뱀이 있는 칸에 도착하면, 뱀을 따라서 내려가게 된다. 즉, 사다리를 이용해 이동한 칸의 번호는 원래 있던 칸의 번호보다 크고, 뱀을 이용해 이동한 칸의 번호는 원래 있던 칸의 번호보다 작아진다. 3. 1번 칸과 100번 칸은 뱀과 사다리의 시작 또는 끝이 아니다. 모든 칸은 최대 하나의 사다리 또는 뱀을 가지고 있으며, 동시에 두 가지를 모두 가지고 있는 경우는 없다. 풀이 1. 비슷한 문제 ( bfs 를 활용한 최단거리 ) 2. 뱀과 사다리에 연연하지 않기 - 한 ..
ps/bfs & dfs 2021. 10. 21. 23:06