[백준_3184] 양_python

https://www.acmicpc.net/problem/3184

3184번: 양

문제

미키의 뒷마당에는 특정 수의 양이 있다. 그가 푹 잠든 사이에 배고픈 늑대는 마당에 들어와 양을 공격했다.

마당은 행과 열로 이루어진 직사각형 모양이다. 글자 '.' (점)은 빈 필드를 의미하며, 글자 '#'는 울타리를, 'o'는 양, 'v'는 늑대를 의미한다.

한 칸에서 수평, 수직만으로 이동하며 울타리를 지나지 않고 다른 칸으로 이동할 수 있다면, 두 칸은 같은 영역 안에 속해 있다고 한다. 마당에서 "탈출"할 수 있는 칸은 어떤 영역에도 속하지 않는다고 간주한다.

다행히 우리의 양은 늑대에게 싸움을 걸 수 있고 영역 안의 양의 수가 늑대의 수보다 많다면 이기고, 늑대를 우리에서 쫓아낸다. 그렇지 않다면 늑대가 그 지역 안의 모든 양을 먹는다.

맨 처음 모든 양과 늑대는 마당 안 영역에 존재한다.

아침이 도달했을 때 살아남은 양과 늑대의 수를 출력하는 프로그램을 작성하라.

입력

첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다.

다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다.

출력

하나의 줄에 아침까지 살아있는 양과 늑대의 수를 의미하는 두 정수를 출력한다.

문제 해결

깊이 우선 탐색으로 울타리마다 양과 늑대의 수를 비교해가며 살아남은 양과 늑대의 각각의 총수를 출력하는 문제이다.

r과 c의 범위를 넘지 않고, '#'을 방문하지 않으며 방문하지 않은 곳만을 방문하는 조건으로 dfs를 구성하였다.

탐색 문제에서 특히 코드를 구성하면서 습관처럼 적었던 코드들에서 오히려 실수를 발생시키는 상황을 마주치면서

def안에서 for문의 위치나 a, b 같은 변수를 전역 변수, 지역변수를 바꿔서  구성해보기도 하고 return을 주고받는 것을 없애고 dfs로만 처리하며 코드를 재구성해보며 여러 연습을 해보았다. 

단편적으로 보면 정말 로직이 쉽게 보이는 간단한 문제이지만 평소 풀던 방법이 아닌 여러 가지 방법을 시도해 볼 수 있는 기초적인 문제였다.

문제 자체의 해결방법이 워낙 다양해 bfs로도 가능하지만 까다로운 조건이 없어 여러 가지 방법으로도 해결할 수 있었다.

깊이 우선 탐색에 대한 이해와 코드를 구성하는 것에 있어서도 조금 더 이해가 깊어져 쉽지만 좋은 문제였다.

import sys
sys.setrecursionlimit(10 ** 6)
r, c = map(int, input().split())
garden = [list(input()) for _ in range(r)]
visited = [[0] * c for _ in range(r)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
sheep = 0
wolves = 0
a,b=0,0
def in_range(x, y):
    return 0 <= x < r and 0 <= y < c
def dfs(x, y):
    global a, b
    #visited[x][y] = True
    if in_range(x, y):
        if garden[x][y] != '#' and visited[x][y] == 0:
            visited[x][y] = True
            if garden[x][y] == 'o':
                a += 1
            if garden[x][y] == 'v':
                b += 1
            for i in range(4):
                nx = dx[i] + x
                ny = dy[i] + y
                dfs(nx, ny)
            return True
        return False

for i in range(r):
    for j in range(c):
        a, b = 0, 0
        if dfs(i, j) == True:
            if a > b:
                sheep += a
            else:
                wolves += b
print(sheep, wolves)