[BOJ/백준 코딩] 양 - PYTHON #3184

소스 코드

def search(i,j):
    global sheep
    global wolf

    temp = []
    temp.append([i,j])

    while len(temp) != 0:
        
        # temp의 값을 하나 뽑아서
        ii,jj = temp.pop(0)

        # 4방향 확인
        for e in range(4):
            N_i = ii + x[e]
            N_j = jj + y[e]

            # 범위 확인
            if 0 <= N_i < R and 0 <= N_j < C:
                
                # 방문 여부 확인
                if visited[N_i][N_j] == 0:
                    
                    # 방문 체크
                    visited[N_i][N_j] = 1
                    
                    # 늑대면 +1하고, temp에 추가
                    if board[N_i][N_j] == 'v':
                        wolf += 1
                        temp.append([N_i,N_j])

                    # 양
                    elif board[N_i][N_j] == 'o':
                        sheep += 1
                        temp.append([N_i,N_j])
                    
                    # 땅
                    elif board[N_i][N_j] == '.':
                        temp.append([N_i,N_j])

    # 양과 늑대의 숫자를 리턴
    return [sheep, wolf]

# 이동 상 하 좌 우
x = [-1,1,0,0]
y = [0,0,-1,1]

# 행, 렬
R,C = map(int,input().split())

# 마당
board = [list(str(input())) for _ in range(R)]

# 방문 확인용
visited = [[0]*C for _ in range(R)]

# 양 결과
res_o = 0

# 늑대 결과
res_v = 0

for q in range(R):
    for w in range(C):
        
        # 양, 늑대, 결과값 초기화
        sheep = 0
        wolf = 0
        res = [0,0]
        
        # 방문 확인
        if visited[q][w] == 0:
            visited[q][w] = 1

            if board[q][w] == 'v':
                wolf += 1
                res = search(q, w)

            elif board[q][w] == 'o':
                sheep += 1
                res = search(q, w)

            elif board[q][w] == '.':
                res = search(q, w)

            else:
                pass

        if res[0] == res[1] == 0:
            pass

        else:
            if res[0] > res[1]:
                res_o += res[0]

            else:
                res_v += res[1]

print(res_o, res_v)

 

---

해결 방법

1) 영역 내의 늑대와 양의 숫자를 확인해야 함

 

2) 울타리를 벗어나지 않고 마당을 탐색하면 영역이 만들어짐

 

==> 울타리를 벗어나지 않으면서 늑대와 양의 숫자를 체크 해주기

3) 늑대와 양의 숫자에 따라 살아남을 수 있는 늑대와 양 결정

4) res_o와 res_v에 값 추가

5) 반복

---

느낀 점

1) 가장 처음 시도했던 방법은 dfs였으나 런타임 오류 발생

( 재귀 한도? 초과 함 reccusion err 발생 )

2) 이후 bfs로 해결

 

3) 주어진 조건(범위)를 잘 확인하고 문제 해결 방법을 결정하자

 

 

 

ps. 개인적인 코드와 코드를 작성의 이유를 적은 것입니다.

 

오류나 적절치 않은 문법이 존재할 수 있으며, 다른 분들께는 굉장히 비효율적인 방법으로 여겨질 수 있습니다.

 

혹시 개선 사항, 오류 및 문제에 대한 수정 사항 등을 댓글로 남겨주신다면 감사한 마음으로 배우고 수정하겠습니다.