문제
미키의 뒷마당에는 특정 수의 양이 있다. 그가 푹 잠든 사이에 배고픈 늑대는 마당에 들어와 양을 공격했다.
마당은 행과 열로 이루어진 직사각형 모양이다. 글자 '.' (점)은 빈 필드를 의미하며, 글자 '#'는 울타리를, 'o'는 양, 'v'는 늑대를 의미한다.
한 칸에서 수평, 수직만으로 이동하며 울타리를 지나지 않고 다른 칸으로 이동할 수 있다면, 두 칸은 같은 영역 안에 속해 있다고 한다. 마당에서 "탈출"할 수 있는 칸은 어떤 영역에도 속하지 않는다고 간주한다.
다행히 우리의 양은 늑대에게 싸움을 걸 수 있고 영역 안의 양의 수가 늑대의 수보다 많다면 이기고, 늑대를 우리에서 쫓아낸다. 그렇지 않다면 늑대가 그 지역 안의 모든 양을 먹는다.
맨 처음 모든 양과 늑대는 마당 안 영역에 존재한다.
아침이 도달했을 때 살아남은 양과 늑대의 수를 출력하는 프로그램을 작성하라.
입력
첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다.
다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다.
출력
하나의 줄에 아침까지 살아있는 양과 늑대의 수를 의미하는 두 정수를 출력한다.
예제
예제 입력 1
6 6
...#..
.##v#.
#v.#.#
#.o#.#
.###.#
...###예제 출력 1
0 2예제 입력 2
8 8
.######.
#..o...#
#.####.#
#.#v.#.#
#.#.o#o#
#o.##..#
#.v..v.#
.######.예제 출력 2
3 1예제 입력 3
9 12
.###.#####..
#.oo#...#v#.
#..o#.#.#.#.
#..##o#...#.
#.#v#o###.#.
#..#v#....#.
#...v#v####.
.####.#vv.o#
.......####.예제 출력 3
3 5문제 접근
울타리 내부에 양고 늑대가 여러 마리 존재할 수 있고 만약 양이 늑대보다 많다면 늑대를 울타리 내부에서 쫓아내고, 그렇지 못한 경우에는 해당 울타리 네 양들이 모두 늑대에게 잡아먹힌다.
따라서, 각 울타리 내부를 탐색할 때 접근 방법은
1. 양과 늑대 마릿수를 각각 count
2. 숫자를 비교하여 승부 결과를 채점하여 울타리 내부의 최종 양과 늑대의 마릿수를 정함
모든 구역을 돌면서 해당 지점이 울타리가 아니라면 울타리 내부라는 뜻이므로, 탐색 시작
탐색의 결과는 양과 늑대의 마릿수를 리턴함
이제 서로의 마릿수를 비교하여 양이 늑대보다 많다면 -> 늑대의 마릿수를 0으로 조정
탐색을 마친 울타리 내부에서 영역에서의 늑대를 모두 쫓아냈다는 뜻이 됨.
또한, 주의할 점은 BFS로 탐색을 시작할 때, 시작점의 경우의 수는 (1) 빈 곳 (2) 양 (3) 늑대 이렇게 3가지가 있으므로 이에 대한 마릿수 상태 관리도 필요합니다.
코드 설명
-
R 및 C는 입력에서 읽혀지며 그리드의 행 및 열 수를 나타냄
그리드(graph)는 한 줄씩 읽혀져서 각 줄이 문자의 리스트로 저장 -
방문한 셀을 추적하기 위한 2차원 배열 visited 생성
dx 및 dy는 가능한 이동을 나타내는 배열로서(오른쪽, 왼쪽, 아래, 위), 초기화됩니다. -
BFS 함수 (BFS):
이 함수는 그리드의 주어진 지점 (x, y)에서 시작하는 너비 우선 탐색을 수행
큐는 시작점으로 초기화되고 양과 늑대의 수를 세기 위한 카운트 시작
그런 다음 BFS를 사용하여 그리드의 연결된 구성 요소를 탐색하고 해당하는 수를 증가
함수는 해당 연결된 구성 요소에서 양과 늑대의 수를 나타내는 튜플을 반환한다.
BFS를 선택한 이유는?
연결된 구성 요소 탐색: 문제에서 각 영역의 양과 늑대의 수를 구해야 합니다. BFS는 시작점에서 출발하여 연결된 구성 요소를 탐색하는 데 효과적입니다. 양과 늑대의 수를 각 영역에서 쉽게 세는 데 활용할 수 있습니다.
최단 경로 탐색이 필요하지 않음: BFS는 최단 경로를 찾는 데 주로 사용되지만, 이 문제에서는 양과 늑대의 상대적 위치만 중요하므로 최단 경로를 찾을 필요가 없습니다. 따라서 간단하면서도 구현이 용이한 BFS가 적절합니다.
-
주요 문제 해결 함수 (solve):
그리드의 각 셀을 반복..
각 방문하지 않은 셀이 벽(#)이 아닌 경우, 해당 셀에서 시작하는 연결된 구성 요소에서 양과 늑대의 수를 세기 위해 BFS 함수를 호출한다. -
각 연결된 구성 요소에서 승자를 결정합니다:
양의 수가 늑대의 수보다 많은 경우 해당 영역에서 늑대는 먹힌 것으로 간주되어 그 수가 0으로 설정된다.
늑대의 수가 양의 수보다 크거나 같은 경우 해당 영역에서 양은 먹힌 것으로 간주되어 그 수가 0으로 설정된다.
양과 늑대의 총합을 누적합..
정답코드
import sys
from collections import deque
input = sys.stdin.readline
R, C = map(int, input().split())
graph = [list(input().rstrip()) for _ in range(R)]
visited = [[False for _ in range(C)] for _ in range(R)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
# 울타리 내부를 BFS 실시
# 양과 늑대의 마리 수를 저장한다. -> 결과 계산
def BFS(x, y):
queue = deque([(x, y)])
visited[y][x] = True
sheep, wolf = 0, 0
# 탐색 시작 점 -> 양 or 늑대 확인
if graph[y][x] == 'o':
sheep += 1
elif graph[y][x] == 'v':
wolf += 1
while queue:
x, y = queue.popleft()
for i in range(4):
next_x, next_y = x + dx[i], y + dy[i]
if 0 <= next_x < C and 0 <= next_y < R: # 범위 확인
if not visited[next_y][next_x] and graph[next_y][next_x] != '#': # 탐색 가능 확인
queue.append([next_x, next_y])
visited[next_y][next_x] = True
# 양 or 늑대에 따라 마리 수 증가
if graph[next_y][next_x] == 'o':
sheep += 1
elif graph[next_y][next_x] == 'v':
wolf += 1
return (sheep, wolf)
def solve():
total_sheep, total_wolf = 0, 0
for x in range(C):
for y in range(R):
if graph[y][x] != '#' and not visited[y][x]:
sheep, wolf = BFS(x, y)
# 해당 울타리 영역 내에서 양이 늑대보다 수가 많다면 이긴다.
if sheep > wolf:
wolf = 0
# 그렇지 않다면 모두 잡아먹힌다.
else:
sheep = 0
total_sheep += sheep
total_wolf += wolf
print(total_sheep, end=' ')
print(total_wolf, end=' ')
solve()시간복잡도
이 코드의 시간 복잡도는 BFS(너비 우선 탐색) 알고리즘이 그리드의 모든 셀을 방문하고, 각 셀당 한 번씩만 방문하기 때문에 O(V + E)이다. 여기서 V는 그래프의 정점 수(셀의 수 = R X C)이며, E는 그래프의 간선 수입니다.
