240420 [BOJ/백준] 3187. 양치기 꿍

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

3187번: 양치기 꿍

---

나의 코드

r, c = map(int, input().split())
arr = [list(input()) for _ in range(r)]
visited = [[0]*c for _ in range(r)]
q = []
di = [0, 1, 0, -1]
dj = [1, 0, -1, 0]

# 울타리로 막히지 않은 영역에는 양과 늑대가 없으므로 제일 끝 줄은 볼 필요 없음
# v: 늑대, k: 양
total_lamb = 0
total_wolf = 0
for i in range(1, r-1):
    for j in range(1, c-1):
        if (arr[i][j] == 'v' or arr[i][j] == 'k') and visited[i][j] == 0:
            lamb_cnt = 0
            wolf_cnt = 0
            if arr[i][j] == 'v':
                wolf_cnt = 1
            else:
                lamb_cnt = 1
            visited[i][j] = 1
            q.append([i, j])

            while q:
                x, y = q.pop(0)
                for k in range(4):
                    ni = x + di[k]
                    nj = y + dj[k]
                    if 1 <= ni < r-1 and 1 <= nj < c-1 and (arr[ni][nj] == 'v' or arr[ni][nj] == '.') and visited[ni][nj] == 0:
                        if arr[ni][nj] == 'v':
                            wolf_cnt += 1
                        visited[ni][nj] = 1
                        q.append([ni, nj])
                    if 1 <= ni < r-1 and 1 <= nj < c-1 and (arr[ni][nj] == 'k' or arr[ni][nj] == '.') and visited[ni][nj] == 0:
                        if arr[ni][nj] == 'k':
                            lamb_cnt += 1
                        visited[ni][nj] = 1
                        q.append([ni, nj])

            if lamb_cnt > wolf_cnt:
                total_lamb += lamb_cnt
            else:
                total_wolf += wolf_cnt

print(total_lamb, total_wolf)

 

결과

---

BFS문제 좋아! 문제 보자마자 이건 바로 풀 수 있겠다 생각했다!

지금까지 풀던 문제와 조금 다른 부분은 값이 v와 k일 때를 나눠서 수를 구해야 했다는 것과 '.'일 때도 계속 코드진행을 해야 한다는 부분이었다.

아무튼 그런 부분을 신경써서 문제를 풀었더니 바로 성공!ㅎㅎ