백준/ Silver 1 문제 , 백준 파이썬 3184 , 양 [BFS]

백준/ Silver 1 문제 , 백준 파이썬 3184 , 양 [BFS]

 

 

풀이 시간

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>

 

문제 출처

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

3184번: 양

 

 

풀이

 

1. 기본 세팅

 

1. 상하좌우 움직임.

 

2. R,C 입력받기

 

3. R행의 MAP 리스트 입력

 

4. visited 선언 (재방문 방지)

 

 

 

 

2. BFS

 

1. 울타리를 제외한 구역을 만나게 되면 bfs 가 호출 된다.

 

2. 호출된 범위에 있는 양들과 늑대들의 수를 카운트 해주는 bfs 함수이다.

 

3. 주의점은 while 문을 돌기 전 호출된 시작부분도 양인지 늑대인지 아니면 땅인지를 구별해서 같이 카운트해주고 visited에 넣어줘야한다.

 

4. 다 돌았을때, 양이 늑대보다 많다면 양의 수를 return 해주고, 늑대의 수가 같거나 많다면 늑대를 return 해준다.

 

5. return 값을 구분하기 위해 문자열도 같이 return 해준다.

 

 

 

 

3. BFS 호출 및 처리

 

리턴 값을 저장 시키기위해 answer=[ 양의 수, 늑대의 수] 를 만들어주고 return 된 값들을 구별하여 해당영역에 맞게 저장시킨다.

 

이후 이 answer 리스트만 출력시켜주면 된다.

 

 

 

 

정답

 

 

from collections import deque
import sys
input=sys.stdin.readline

vertical=[1,-1,0,0]
parallel=[0,0,1,-1]

R,C=map(int,input().split())
MAP=[list(map(str,input())) for _ in range(R)]
visited=[[False for _ in range(C)] for _ in range(R)]

def bfs(x,y):
    dq=deque()
    dq.append([x,y])
    wolf=0
    sheep=0
    if MAP[x][y]=='v':
        wolf+=1
    elif MAP[x][y]=='o':
        sheep+=1
    visited[x][y]=True
    while dq:
        X,Y=dq.popleft()
        for i in range(4):
            mx,my=X+vertical[i],Y+parallel[i]
            if 0<=mx<R and 0<=my<C:
                if visited[mx][my]==False:
                    if MAP[mx][my]=='.':
                        dq.append([mx,my])
                        visited[mx][my]=True
                    elif MAP[mx][my]=='v':
                        wolf+=1
                        dq.append([mx,my])
                        visited[mx][my]=True
                    elif MAP[mx][my]=='o':
                        sheep+=1
                        dq.append([mx,my])
                        visited[mx][my]=True
    if sheep==0 and wolf==0:
        return ['None',0]
    elif sheep>wolf:
        return ['sheep',sheep]
    else:
        return ['wolf', wolf]

answer=[0,0]
for i in range(R):
    for j in range(C):
        if visited[i][j]==False:
            if MAP[i][j]=='.' or MAP[i][j]=='v' or MAP[i][j]=='o':
                result=bfs(i,j)
                if result[0]=='sheep':
                    answer[0]+=result[1]
                elif result[0]=='wolf':
                    answer[1]+=result[1]

print(*answer)