[Goorm/Python] 발전기 (2) || 구름톤 챌린지 (DFS, BFS)

구름톤 챌린지 발전기 (2) 파이썬

구름LEVEL

❏ 문제 설명

❍ 문제

구름 심시티를 하고 있는 플레이어는 한 변의 길이가 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)

이 문제에서 좀 더 나아가서 조건을 더 체크해줘야 하는 문제이다.

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를 사용하여, 해당 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 이라는 한 줄을 삭제하고 나서 통과할 수 있었다.