알고리즘 풀이/그래프
-
백준 17822번 원판 돌리기 :: 마이구미알고리즘 풀이/그래프 2019. 12. 28. 20:11
이 글은 백준 알고리즘 문제 17822번 "원판 돌리기" 를 풀이한다. 2019 삼성 SW 테스트 문제 중 하나이다. 단순히 시뮬레이션으로 풀 수도 있으나, DFS 또는 BFS 를 활용할 수 있는 문제이다. DFS, BFS - https://mygumi.tistory.com/102 문제 링크 - https://www.acmicpc.net/problem/17822 본인은 처음 이 문제를 접근할 때, 많은 고민을 했다. 그런데 사실 이 문제는 사실 정답률에 비해, 크게 어렵지도 복잡하지도 않다. 그 이유는 고민할 게 크게 없었고, 테스트 케이스도 작아서, 어떻게 구현해도 시간 초과를 초래하지 않을 거라 판단했다. 그래서 "어떤 함정이 있을까?" 라는 의심에 시간을 좀 썼다. 사실 의심할 건 크게 없고, 이해..
-
백준 17142번 연구소 3 :: 마이구미알고리즘 풀이/그래프 2019. 6. 3. 20:31
이 글은 백준 알고리즘 문제 17142번 "연구소 3" 를 풀이한다. 삼성 SW 역량 테스트 문제이다. 문제 해결을 위해 DFS, BFS 2가지 모두 요구한다. 문제 링크 - https://www.acmicpc.net/problem/17142 DFS, BFS - https://mygumi.tistory.com/102 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 모두 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며,..
-
백준 16236번 아기 상어 :: 마이구미알고리즘 풀이/그래프 2018. 12. 7. 17:27
이 글은 백준 알고리즘 문제 16236번 "아기 상어" 를 풀이한다.삼성 SW 출제 문제로써, 탐색 문제이다.문제 링크 - https://www.acmicpc.net/problem/16236BFS, DFS - http://mygumi.tistory.com/102 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신..
-
백준 16234번 인구 이동 :: 마이구미알고리즘 풀이/그래프 2018. 11. 25. 14:52
이 글은 백준 알고리즘 문제 16234번 "인구 이동" 을 풀이한다.문제는 BFS 를 통해 풀이한다.삼성 SW 역량 테스트에서 출제된 문제이다.문제 링크 - https://www.acmicpc.net/problem/16234BFS - http://mygumi.tistory.com/102 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.오늘부터 인구 이동이 시작되는 날이다.인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.국경선을 공유하는 ..
-
백준 1325번 효율적인 해킹 :: 마이구미알고리즘 풀이/그래프 2018. 11. 21. 00:44
이 글은 백준 알고리즘 문제 1325번 "효율적인 해킹" 을 풀이한다.문제는 DFS 를 통해 접근한다.DFS 가 익숙하지 않는다면, 아래 관련 링크를 읽어보면 좋다.문제 링크 - https://www.acmicpc.net/problem/1325DFS - http://mygumi.tistory.com/102- 현재 코드(Java)는 최근 재채점으로 인해 시간초과를 발생시킨다 해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할..
-
백준 2479번 경로 찾기 :: 마이구미알고리즘 풀이/그래프 2018. 1. 29. 21:15
이 글은 백준 알고리즘 문제 11403번 "경로 찾기" 를 풀이한다.정올 출제 문제로써, 풀이 방법은 DFS 를 통해 해결한다.문제 링크 - https://www.acmicpc.net/problem/2479DFS - https://mygumi.tistory.com/102 길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자. 이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 예를 들어, A=010010, B=011011 이라고 하면, 세 번째 비트와 여섯 번째 비트만 서로 다르므로 이 두 코드 사이의 해밍 거리는 2이다.우리는 총 N개의 이진 코드를 가지고 있고, 각 코드의 길이는 K로 같다.예를 들어, 다음과 같이 길이..
-
백준 1799번 비숍 :: 마이구미알고리즘 풀이/그래프 2018. 1. 29. 20:16
이 글은 백준 알고리즘 문제 1799번 "비숍" 을 풀이한다.정올 문제로써, 풀이 방법은 DFS 를 통해 해결한다.문제 링크 - https://www.acmicpc.net/problem/1799DFS - http://mygumi.tistory.com/102 서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. 과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다.그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. 에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 과 같이 최대 7개의 비숍을 놓을 수 있..
-
백준 2589번 보물섬 :: 마이구미알고리즘 풀이/그래프 2018. 1. 28. 18:05
이 글은 백준 알고리즘 문제 2589번 "보물섬" 을 풀이한다.풀이 방법으로는 BFS(너비 우선 탐색) 을 이용한다.문제 링크 - https://www.acmicpc.net/problem/2589BFS - http://mygumi.tistory.com/102 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이..