문제20. 연결 요소 제거하기 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 문제 해결 방법 4주 동안의 구름톤 챌린지의 막을 내리는 문제이다. 지금까지의 문제들을 잘 풀었다면, 오늘 문제도 어렵지 않게 풀 수 있는 DFS/BFS 문제였다. 상하좌우 4가지 방향에 있는 칸들에 대해, 입력받은 p와 같은 경우에만 BFS/DFS를 이용해 파급이 되도록 만들면 된다. 파급이 되는 동안 방문하지 않은 곳이라면 count 를 올려주고, 방문한 곳이라면 해당 칸은 스킵한다. 파급이 끝나면 count의 개수에 따라 "."으로 해당 칸을 바꿀지를 결정하면 된다. 위 내용을 코드로 구현하면 아래와 같다. import sys from collections ..
BFS
문제19. 대체 경로 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 문제 해결 방법 가중치가 없는 그래프의 최단 경로 탐색 방법에 대한 문제이다. 가중치가 있는 그래프에 대해서는 다익스트라 알고리즘, 벨만-포드 알고리즘, 플루이드 워샬 알고리즘 등을 고려해야 했겠지만, 가중치가 없는 그래프에 대해서는 BFS만을 이용해서 해결할 수 있다. BFS 알고리즘의 특성상, 먼저 큐에 들어간 노드부터 큐에서 꺼내어 쓰기 때문에, 출발지로부터 같은 거리만큼 떨어진 노드는 같은 타이밍에 큐에서 꺼내지게 된다. 당연한 말이지만, 더 멀리 떨어진 노드를 탐색하려면, 가까웠던 노드를 통해서 가야하기 때문에 더 멀리 떨어진 노드보다 가까이에 있는 노드가 더 먼..
문제17. 통신망 분석 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 문제 해결 방법 오늘 문제는 그래프 표현 방법들을 알고 있고, 어떤 표현 방식이 적절한지를 판단할 수 있어야 풀 수 있는 문제였다. 오늘 문제의 컴퓨터의 개수, 즉 노드의 개수는 최대 100,000 개이다. 이를 인접행렬을 이용해서 풀기 위해서는 N * N의 이차원 배열이 필요하므로 사용하게 되는 공간은 최대 100,000 * 100,000 = 10,000,000,000 이다. 실제로 인접 행렬 방식으로 문제를 풀어 제출하면, 많은 수의 테스트 케이스에서 Runtime Error가 나는데, 이는 메모리 초과로 인해 발생한 에러이다. 시간적인 문제도 있다. 문제 조건을 보..
문제13. 발전기 (2) 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 문제 해결 방법 오늘 구름톤 챌린지 문제는 어제와 사실상 같은 문제이다. 다만 어제는 1과 0 두 가지 경우로만 고려했다면, 오늘 문제는 1~30의 임의의 수를 고려해야하는 문제이다. 문제를 복잡하게 설명해서 이해하기 어렵지만, 같은 유형 건물이 k 개 이상 붙어있는 곳은 단지가 되고, 가장 많은 단지가 형성된 건물의 유형을 구하면 되는, 사실은 간단한 요구사항을 가진 문제이다. 어제와 같이 BFS를 적용하되 어제는 count를 설치할 발전소의 숫자로 하였다면, 오늘은 k개 이상의 건물이 서로 인접해 있는지를 판단하기 위해, 인접한 건물의 수를 세기 위한 변수로 cou..
문제12. 발전기 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 문제 해결 방법 이차원 리스트의 각 칸들을 전부 돌면서, 1이라면(전력공급이 아직 안됐다면) 발전기를 설치하는 문제이다. 중요한 것은 전력이 공급된 곳의 상하좌우에 있는 집도 전력이 공급된다는 것이다. 즉, 발전기를 하나 설치할 때, 연쇄적으로 영향받는 집이 있는지를 체크해줘야한다는 것이다. 가장 먼저 생각할 수 있는 것은 재귀함수이다. 전력이 공급된 집의 상하좌우 집들에도 전력 공급이 되고, 또 전력을 공급받은 집의 상하좌우 집들에 전력이 공급된다. 이러한 구조는 재귀로 간단하게 구현할 수 있다. 아래 코드와 같이 상하좌우 집들 중에 아직 전력이 공급되지 않은 집에 한해서 ..
