구름톤 챌린지 발전기 (2) 파이썬
구름LEVEL
난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다.
level.goorm.io
❏ 문제 설명
❍ 문제
구름 심시티를 하고 있는 플레이어는 한 변의 길이가 N인 정사각형 모양의 마을 M을 만들고 있다. 마을의 모든 칸에는 건물이 하나씩 있고, r번째 행, c번째 열에 해당하는 칸에는 정수 $M_{r, c}$가 적혀 있다. $M_{r, c}$는 해당 칸에 있는 건물의 유형의 번호를 의미한다.
건물의 유형이 동일하면서, 서로 상하좌우 인접한 칸에 위치한 건물끼리는 서로 전력을 공유할 수 있다. 전력을 공유할 수 있는 관계에 속한 건물의 개수가 K개 이상이면 이를 단지라고 한다.
플레이어는 발전기를 설치해 각 단지에 전력을 공급하고자 한다. 하지만 비용 문제로 인해 단 하나의 발전기만 설치할 수 있다. 발전기는 특정 건물 유형 하나에 해당하는 모든 단지에 전력을 공급할 수 있다. 그래서 플레이어는 가장 많은 단지가 있는 건물 유형에 전력을 공급할 것이다. 만약 그러한 건물 유형이 여러 개라면, $M_{r, c}$가 더 큰 건물 유형에 전력을 공급한다.
플레이어가 전력을 공급해야 할 건물의 유형 번호를 구해보자.
❍ 입력
첫째 줄에 마을의 크기 N과 단지의 기준 K가 공백을 두고 주어진다.
다음 N개의 줄에는 마을의 상태를 나타내는 N개의 숫자가 공백을 두고 주어진다.
r번째 줄에서 c번째로 주어지는 값이 $M_{r, c}$에 해당한다.
- $1 \leq N \leq 1000$
- $1 \leq K \leq 50$
- $1 \leq M_{r, c} \leq 30$
- 최소 하나 이상의 단지가 있는 입력만 주어진다.
- 주어지는 모든 수는 정수이다.
❍ 출력
플레이어가 전력을 공급해야 할 건물의 유형 번호를 출력한다.
❏ 문제 풀이
< 발전기 >
[Goorm/Python] 발전기 || 구름톤 챌린지 (DFS, BFS)
구름톤 챌린지 발전기 파이썬 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 더보기 ❍ 문제 구름 심시티를 하고 있는 플레이어는 한 변의 길이가 N
dmaolon00.tistory.com
이 문제에서 좀 더 나아가서 조건을 더 체크해줘야 하는 문제이다.
BFS로 풀이를 먼저 해주었다.
❍ 변수 설명
n, k = map(int, input().split())
village = [list(map(int, input().split())) for _ in range(n)]
visited = [[False] * n for _ in range(n)]
type = {}
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for i in range(n):
for j in range(n):
# 방문하지 않은 건물인 경우
if not visited[i][j]:
# type에 없는 건물 유형인 경우, 추가하기
if village[i][j] not in type:
type[village[i][j]] = 0
# 방문 처리 후, bfs 탐색 시작
visited[i][j] = True
bfs(i, j, village[i][j])type의 경우 dictionary를 사용하여 건물 유형과 해당 유형에 대한 단지 개수를 넣어주고자 하였다.
이중 for문으로 마을을 돌아다니며, 방문하지 않은 건물이 존재한다면, 해당 건물의 유형을 파악하고, 방문 처리를 해준다. 그 후 해당 건물에 인접한 건물을 찾기 위해 bfs 탐색을 진행한다.
여기서 태호가 알려준 defaultdict를 새롭게 알게 되었다.
Defaultdict, Counter, bisect
Defaultdict from collections import defaultdict counter = defaultdict(int) 기본 dict는 해당 키 값이 있는지 없는지 확인을 해야 한다. ex) if 2 not in dict: dict[2] =0 , 하지만 defaultdict는 위의 코드처럼 생성자를 사용해
te-ho.tistory.com
defaultdict를 사용하여, 해당 key가 이미 dict에 존재하는지를 자동으로 확인해주어 편리한 것 같다.
따라서 아래와 같이 사용해주었다.
n, k = map(int, input().split())
village = [list(map(int, input().split())) for _ in range(n)]
visited = [[False] * n for _ in range(n)]
type = defaultdict(int)
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for i in range(n):
for j in range(n):
if not visited[i][j]:
type[village[i][j]]
visited[i][j] = True
bfs(i, j, village[i][j])type[village[i][j]] 처럼 값을 지정하지 않았을 때, 존재하지 않는 경우엔 자동으로 0이 value로 들어가게 된다.
❍ BFS
def bfs(x, y, t):
queue = deque()
queue.append((x, y))
count = 1
while queue:
x, y = queue.popleft()
for dx, dy in direction:
nx, ny = x + dx, y + dy
# 마을 밖인 경우 + 건물 유형(t)이 다른 경우 + 이미 방문한 경우
if (
nx in (-1, n)
or ny in (-1, n)
or village[nx][ny] != t
or visited[nx][ny]
):
continue
# 방문 처리 + 큐 추가 + 건물 수 증가
visited[nx][ny] = True
queue.append((nx, ny))
count += 1
# 건물의 수가 k가 된다면 이를 단지라고 한다. 단지의 개수 + 1
if count == k:
type[t] += 1큐에 시작 건물를 담고 count를 1로 초기화를 한다.
그 후에 큐에서 건물을 꺼내며 상하좌우를 조건에 맞는지 확인하고, 방문 처리를 하고 큐에 담는다. count도 1 증가시킨다.
만약 count가 k와 동일하여 단지가 될 수 있을 때, 그 때 type에서 해당 건물 유형의 개수를 + 1 해준다.
❍ CODE_BFS
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
def bfs(x, y, t):
queue = deque()
queue.append((x, y))
count = 1
while queue:
x, y = queue.popleft()
for dx, dy in direction:
nx, ny = x + dx, y + dy
# 마을 밖인 경우 + 건물 유형(t)이 다른 경우 + 이미 방문한 경우
if (
nx in (-1, n)
or ny in (-1, n)
or village[nx][ny] != t
or visited[nx][ny]
):
continue
# 방문 처리 + 큐 추가 + 건물 수 증가
visited[nx][ny] = True
queue.append((nx, ny))
count += 1
# 건물의 수가 k가 된다면 이를 단지라고 한다. 단지의 개수 + 1
if count == k:
type[t] += 1
n, k = map(int, input().split())
village = [list(map(int, input().split())) for _ in range(n)]
visited = [[False] * n for _ in range(n)]
type = defaultdict(int)
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for i in range(n):
for j in range(n):
if not visited[i][j]:
type[village[i][j]]
visited[i][j] = True
bfs(i, j, village[i][j])
type = list(type.items())
type.sort(key=lambda x: (-x[1], -x[0]))
print(type[0][0])
❍ CODE_DFS
비재귀 DFS로 풀이를 해주었다.
import sys
from collections import defaultdict
input = sys.stdin.readline
def dfs(x, y, t):
stack = [(x, y)]
count = 1
while stack:
x, y = stack.pop()
for dx, dy in direction:
nx, ny = x + dx, y + dy
# 마을 밖인 경우 + 건물 유형(t)이 다른 경우 + 이미 방문한 경우
if (
nx in (-1, n)
or ny in (-1, n)
or village[nx][ny] != t
or visited[nx][ny]
):
continue
visited[nx][ny] = True
stack.append((nx, ny))
count += 1
if count == k:
type[t] += 1
n, k = map(int, input().split())
village = [list(map(int, input().split())) for _ in range(n)]
visited = [[False] * n for _ in range(n)]
type = defaultdict(int)
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for i in range(n):
for j in range(n):
if not visited[i][j]:
type[village[i][j]]
visited[i][j] = True
dfs(i, j, village[i][j])
type = list(type.items())
type.sort(key=lambda x: (-x[1], -x[0]))
print(type[0][0])❏ 삽질 기록
❍ Issue #1
import sys
from collections import deque
input = sys.stdin.readline
def bfs(x, y, t):
queue = deque()
queue.append((x, y))
count = 1
while queue:
x, y = queue.popleft()
for dx, dy in direction:
nx, ny = x + dx, y + dy
# 마을 밖인 경우 + 건물 유형(t)이 다른 경우 + 이미 방문한 경우
if (
nx in (-1, n)
or ny in (-1, n)
or village[nx][ny] != t
or visited[nx][ny]
):
continue
visited[nx][ny] = True
queue.append((nx, ny))
count += 1
if count == k:
count = 0
type[t] += 1
n, k = map(int, input().split())
village = [list(map(int, input().split())) for _ in range(n)]
visited = [[False] * n for _ in range(n)]
type = {}
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for i in range(n):
for j in range(n):
if not visited[i][j]:
if village[i][j] not in type:
type[village[i][j]] = 0
visited[i][j] = True
bfs(i, j, village[i][j])
result = 0
max_value = 0
for x, y in type.items():
if y >= max_value:
max_value = y
if y == max_value:
result = max(result, x)
type = list(type.items())
type.sort(key = lambda x : (-x[1], -x[0]))
print(type[0][0])마지막에 가장 많은 단지를 가진 건물 유형을 구하는 코드에서 고민을 좀 했는데, 이 부분에서 문제가 생긴 것은 아닌 것 같다. 무언가를 빼먹은 게 존재하는 것 같은 느낌이었다.
빼먹어야 할 거를 넣은 것이 문제임을 알게 되었다.
count가 k와 동일해 질 때, type에 해당하는 단지 개수를 1 증가 시키는 것이기 때문에, count를 0으로 초기화할 필요가 없다.
오히려 count가 k의 2배일 경우에는 초기화로 인해서 한번 더 추가될 수 있기 때문에 count = 0 이라는 한 줄을 삭제하고 나서 통과할 수 있었다.