[파이썬] 백준 3184, 3187 : 양, 양치기 꿍 (실버1)

[파이썬] 백준 3184, 3187 : 양, 양치기 꿍 (실버1)

 

3184번: 양

 

3187번: 양치기 꿍

 

---

풀이

0. 방향성 생각

주어진 영역 내에서 양, 늑대의 수를 세서 계산.

탐색 가능한 영역이면 DFS로

1. 입력

import sys
sys.setrecursionlimit(10**6)
input = lambda: sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = [list(input()) for _ in range(h)]

 

2. 함수 정의

def dfs(x,y,sheep,wolf):
    if x<0 or x>=w or y<0 or y>=h:
        return sheep,wolf
    if arr[y][x] != '#':
        if arr[y][x] == 'v': wolf += 1
        elif arr[y][x] == 'o': sheep += 1
        arr[y][x] = '#'
        
        step = [[1,-1,0,0],[0,0,1,-1]]
        for i in range(4):
            nx = x + step[0][i]
            ny = y + step[1][i]
            sheep,wolf = dfs(nx,ny,sheep,wolf)
    return sheep,wolf

3. 출력

# 양
a,b = 0,0
for s,w in result:
    if s<=w : b += w
    else : a += s
print(a,b)

# 양치기 꿍
a,b = 0,0
for s,w in result:
    if s>w : a += s
    else : b += w
print(a,b)

---

전체코드

import sys
sys.setrecursionlimit(10**6)
input = lambda: sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = [list(input()) for _ in range(h)]

def dfs(x,y,sheep,wolf):
    if x<0 or x>=w or y<0 or y>=h:
        return sheep,wolf
    if arr[y][x] != '#':
        if arr[y][x] == 'v': wolf += 1
        elif arr[y][x] == 'o': sheep += 1
        arr[y][x] = '#'
        
        step = [[1,-1,0,0],[0,0,1,-1]]
        for i in range(4):
            nx = x + step[0][i]
            ny = y + step[1][i]
            sheep,wolf = dfs(nx,ny,sheep,wolf)
    return sheep,wolf

result = []
for i in range(h):
    for j in range(w):
        if arr[i][j] != '#':
            result.append(dfs(j,i,0,0))
            
# 양
a,b = 0,0
for s,w in result:
    if s<=w : b += w
    else : a += s
print(a,b)

# 양치기 꿍
a,b = 0,0
for s,w in result:
    if s>w : a += s
    else : b += w
print(a,b)

코멘트

dfs 인수로 양 늑대수 넣어서 그런지 몰라도 성능이 나쁘다.

태그 찾아서 DFS로 풀었는데 굳이 DFS로 풀어야 하는지 모르겠다.