문제 풀이 이 문제는 두가지 풀이법이 있다. top-down 방식으로 b를 a로 만들어가는 방식과 bottom-up 방식으로 a를 b로 만드는 bfs방식이 있다. 문제에서 a를 b로 만들어가는 방식에는 x2 연산과 끝자리에 1을 붙여가는 방식이 있다. 즉, b가 짝수이거나 끝자리가 1인 경우만 a를 통해 만들 수 있다. top-down 방식으로 푸는 경우는 이런 과정을 통해 수행된다. bottom-up 방식의 bfs 방식은 연산의 수행과정을 큐에 계속 넣어가면서 답을 찾는 과정을 수행한다. 풀이 코드 top-down 방식 bfs를 이용한 방식

문제 풀이 BFS를 사용하면 쉽게 풀 수 있는 문제이다. 각 영역들의 좌표를 이용하여 직사각형이 그려진 영역은 1로 채우고 나머지 영역은 0으로 채워둔다. 0으로 채워져 있는 영역의 넓이를 구하고 더 구하지 못할 때 리스트에 추가하는 방식으로 각 영역의 넓이를 리스트에 채우면 된다. 풀이 코드

문제 풀이 어려운 문제였다. 벽을 부수며 이동하였을 때 벽을 부순 경우와 부수지 않았을 경우를 어떻게 나누어야 하는지 한참을 고민했는데 결국 스스로 해결하진 못했다.. 다른 풀이를 참고한 결과 visited 배열에 벽을 부쉈을 경우를 추가하여 3차원 배열로 만들어 해결할 수 있었다. 벽을 부수지 않고 이동하면 0을 저장하고 부쉈을 경우에는 1을 저장하며 진행한다. 부수지 않았을 경우와 부쉈을 경우를 계속해서 큐에 넣어가며 진행하면서 먼저 가장 끝에 도착하였을때의 이동 칸수를 출력하면 된다. 풀이 코드

문제 풀이 전형적인 bfs 문제다. bfs로 계속해서 노드를 탐색하고 visit 배열에 노드를 방문하기 위해 거친 edge의 개수를 저장해가며 탐색하면 쉽게 답을 구할 수 있다. 풀이 코드

문제 풀이 이

문제 풀이 bfs를 사용해서 문제를 풀면 되지만 바이러스가 퍼지는 순서가 정해져 있으며 정해진 시간만큼만 퍼진다는 조건 때문에 조금 까다로웠다. 가장 초기상태의 바이러스 위치들을 입력받는다. 바이러스 숫자, x좌표, y좌표를 입력받고 바이러스 숫자에 맞춰 정렬한다. 그 정렬한 리스트를 큐에 넣는다. 그대로 bfs를 진행하는데 바이러스의

문제 풀이 우선 문제 자체는 전체 연구소 지도에 벽 3개를 세워 바이러스가 퍼지는 공간을 최소화 하는 문제이다. 언뜻 보기에 쉬워보였지만 생각보다 애를 먹었다. BFS를 이용해서 벽을 세운 뒤의 안전구역을 세는 건 손쉽게 작성했지만 벽을 세우는 부분에서 막혀버렸다. 결국 다른 사람의 코드를 참고하고 나서야 함수를 재귀적으로 활용하면 된다는 걸 깨달았다. 안전구역을 찾는 bfs함수는 기본적인 bfs 방식을 그대로 사용하면 되는데 벽을 새로 세울 때마다 안전구역을 다시 확인해야 하기 때문에 test_lab을 깊은 복사로 복사해야한다. 벽을 세우는 wall함수에서는 벽의 개수를 cnt로 하고 한번 세울 때마다 cnt를 증가시켜가며 wall함수를 재귀호출 함수를 재귀호출 한

문제 풀이 이것이 코딩테스트다에 수록되어있는 미로찾기 문제와 유사한 문제로 BFS를 이용하면 풀 수 있다. 이처럼 그래프에서 간선의 비용이 동일할 때 BFS를 이용하면 최단거리를 찾는 문제의 해답에 쉽게 접근할 수 있다. 특정 도시 x를 시적으로 BFS를 수행한다. 특정 도시에서 도달할 수 있는 도시들을 next에 할당한다. next 도시가 -1의 값을 가질 경우 출발지점에서 now 지점의 도시에 도달하는 최단 거리에 1을 더해 next도시에 할당한다. 모든 경우에 대해 BFS를 수행한 뒤에 최단거리가 k인 값들을 오름차순으로 출력하면 된다. 정답 코드

문제 >N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. 입력 첫째 줄에 두 정수 N, M(4 입력 예시 5 6 101010 111111 000001 111111 111111 출력 예시 10 풀이 이 문제는 bfs를 이용해서