구름을 채우다

문제 보기 이 문제는 BFS와 시뮬레이션 문제이다. 갈수록 삼성 SW 역량 테스트의 문제가 점점 더 구현에 까다로운 조건을 추가하기 시작하는 게 느껴진다. 먼저, 문제를 풀기 위해 원판의 숫자를 어떻게 표현할 것인지에 대해서 생각해보아야 한다. 문제에서 주어진 원판을 행렬로 표현하면 다음과 같다. 이제 원판을 행렬로 나타냈으니, 원판을 회전시키는 함수를 작성한다. i번째의 원판을 회전시킬 때, i의 배수인 원판 모두 회전을 시켜야 한다. 이 부분에 대한 구현은 13~27번째 줄에 다음과 같이 구현되어 있다. def rotate(_x, _d, _k): # rotate counter-clockwise if _d: # for all disks which is multiple of x for i in range..

문제 보기 이 문제는 DFS, BFS 문제이다. (DFS로는 안 풀어도 된다.) 연구소 내의 모든 바이러스 중에서 m개의 바이러스를 선택하는 과정을 DFS로 풀면 DFS 문제가 되겠지만, 나는 itertools 모듈의 combinations 함수를 사용하였다. 문제를 푼 로직은 다음과 같다. 입력으로부터 연구소 내의 빈 방의 개수와 바이러스의 위치를 저장한다. (9~17번째 줄) 모든 바이러스 중에서 m개의 바이러스를 선택하는 모든 경우의 수를 구한다. (20~21번째 줄) 2번에서 구한 m개의 바이러스를 큐에 삽입한다. (22~26번째 줄) 3번에서 큐에 삽입한 m개의 바이러스를 BFS를 통해 확산시킨다. (확산될 수 있는 경우의 수는 빈 방일 경우와 비활성 바이러스일 경우 확산될 수 있다. 빈 방의 ..

문제 보기이 문제는 백준에 알고리즘 분류가 따로 되어있지 않지만 나는 BFS로 푼 문제이다.상어가 먹을 물고기를 찾기 위해서 BFS를 사용하였고, 상어가 어디로 이동할 지 결정하는 방법은 다음과 같다.먹을 물고기를 정하기 위해서 나는 우선순위 큐(Priority Queue)를 사용했다.문제를 풀기 위한 로직은 다음과 같다. 1. 현재의 상어위치로부터 BFS를 시작한다. (17~20번째 줄)2. BFS를 진행하면서, 상어가 지나갈 수 있으면 현재까지의 거리, 행과 열을 큐에 넣고, 먹을 수 있는 물고기가 있으면 우선순위 큐에 우선순위를 현재까지의 거리, 행, 열 순으로 삽입한다. (30~36번째 줄)3-1. 우선순위 큐가 비어있으면(=먹을 수 없는 물고기가 없으면) 종료한다. (38~40번째 줄)3-2. ..

문제 보기백준에 이 문제는 따로 알고리즘 분류가 없지만, 나는 BFS로 푼 문제이다. 두 나라의 인구가 이동하는 조건은 다음과 같다.위에 해당하는 단계들이 1번의 인구이동이다.여기서 실수할 수 있는 부분이 있다.나는 문제를 풀 때, 한 개의 연합국에서 인구이동이 끝날 때 1번의 인구이동이라고 카운트를 세었지만, 정답은 주어진 맵에서 가능한 모든 연합국들의 인구이동이 끝나는 것이 1번의 인구이동이었다.따라서 문제를 해결하기 위한 로직은 다음과 같다. 1. 주어진 맵의 각 위치마다 BFS를 진행한다. 이 때, 한 번의 인구이동동안 연합국에 해당하는지 확인하기 위한 집합 변수(unions)를 둔다. (11번째 줄)2. 연합국이 아닌 모든 나라들에 대해서 BFS를 진행한다. (12~33번째 줄)3. 한 번의 B..

문제 보기이 문제도 BFS와 브루트 포스를 합친 문제이다.처음에 문제를 읽었을 때, 완전탐색을 해야하지만 무엇을 완전탐색 해야할 지 감이 잡히지 않았다.계속 고민을 하다보니, 상, 하, 좌, 우로 블록들을 이동시켰을 때의 판의 상태를 완전탐색해야겠다고 생각했다. BFS 부분은 그래프 내에서 최대값을 구하는 알고리즘과 동일하다. 구현 상의 어려운 부분은 moveBoard 메소드인데, 블록들을 이동시켰을 때의 상태를 새로운 판 객체로 반환해서, 이를 큐에 추가하는 것이다. 문제는 최대 5번 이동시켜서 얻을 수 있는 최댓값을 구하는 것이기 때문에, 5번이 넘어가면 BFS를 중단하고 결과값을 반환한다. 판 객체를 큐에 추가한다는 개념은 아래의 그림을 보면 이해하기 쉽다. 위 그림은 블록들을 1번 이동시켰을 때의..

문제 보기이 문제는 BFS에 브루트포스를 응용한 문제이다.처음에 문제를 읽을 당시에는 어떻게 코드를 짜야할 지 몰랐지만, 질문게시판을 뒤지다 보니 영감을 얻었다.한 번 방문할 때마다 각 방향을 탐색하는 건 기존의 BFS 동일하다.하지만 판을 기울일 때 벽, 구멍 또는 다른 공에 닿을 때까지 직진을 해야한다는 것에 주의해야 한다. 또 주의해야할 점은, 두 개의 공을 굴려서 같은 곳에서 멈추는 경우에는, 공이 굴러간 거리를 계산한 뒤, 굴러간 거리가 더 긴 공을 다시 굴러왔던 방향으로 1번 이동해야 한다. (그렇게 해야 공이 겹치지 않는다. 60~65번째 줄 참고) 67~69번째 줄을 보면 다음과 같은데, 이 부분의 코드가 없으면 count가 11이상이 되는 반례가 생긴다. # prevent count fr..

문제보기해당 문제는 브루트포스와 BFS를 조합한 문제이다.문제를 풀기 위해, 세워야 하는 벽의 갯수는 반드시 3개여야 하며, 안전 영역 크기의 최댓값을 구해야 한다. 이를 통해서 벽을 세울때는 반드시 겹치면 안되며, 벽의 위치의 조합을 구해야 하고, 해당 조합은 안전구역에서 겹치지 않는 3개의 위치여야 한다는 것을 알 수 있다..게다가 주어진 입력값의 범위가 크지 않은 3