JB의 이모저모

[BOJ 18809 🥇1] Gaaaaaaaaaarden (Python) 본문

알고리즘/백준

[BOJ 18809 🥇1] Gaaaaaaaaaarden (Python)

J B 2023. 9. 25. 00:19

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

 

18809번: Gaaaaaaaaaarden

첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두

www.acmicpc.net

문제

길고 길었던 겨울이 끝나고 BOJ 마을에도 봄이 찾아왔다. BOJ 마을에서는 꽃을 마을 소유의 정원에 피우려고 한다. 정원은 땅과 호수로 이루어져 있고 2차원 격자판 모양이다.

인건비 절감을 위해 BOJ 마을에서는 직접 사람이 씨앗을 심는 대신 초록색 배양액과 빨간색 배양액을 땅에 적절하게 뿌려서 꽃을 피울 것이다. 이 때 배양액을 뿌릴 수 있는 땅은 미리 정해져있다.

배양액은 매 초마다 이전에 배양액이 도달한 적이 없는 인접한 땅으로 퍼져간다.

아래는 초록색 배양액 2개를 뿌렸을 때의 예시이다. 하얀색 칸은 배양액을 뿌릴 수 없는 땅을, 황토색 칸은 배양액을 뿌릴 수 있는 땅을, 하늘색 칸은 호수를 의미한다.

초록색 배양액과 빨간색 배양액이 동일한 시간에 도달한 땅에서는 두 배양액이 합쳐져서 꽃이 피어난다. 꽃이 피어난 땅에서는 배양액이 사라지기 때문에 더 이상 인접한 땅으로 배양액을 퍼트리지 않는다.

아래는 초록색 배양액 2개와 빨간색 배양액 2개를 뿌렸을 때의 예시이다.

배양액은 봄이 지나면 사용할 수 없게 되므로 주어진 모든 배양액을 남김없이 사용해야 한다. 예를 들어 초록색 배양액 2개와 빨간색 배양액 2개가 주어졌는데 초록색 배양액 1개를 땅에 뿌리지 않고, 초록색 배양액 1개와 빨간색 배양액 2개만을 사용하는 것은 불가능하다.

또한 모든 배양액은 서로 다른 곳에 뿌려져야 한다.

정원과 두 배양액의 개수가 주어져있을 때 피울 수 있는 꽃의 최대 개수를 구해보자.

입력

첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두고 주어진다.

그 다음 N개의 줄에는 각 줄마다 정원의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0, 1, 2이다. 0은 호수, 1은 배양액을 뿌릴 수 없는 땅, 2는 배양액을 뿌릴 수 있는 땅을 의미한다.

배양액을 뿌릴 수 있는 땅의 수는 R+G개 이상이고 10개 이하이다.

출력

첫째 줄에 피울 수 있는 꽃의 최대 개수를 출력한다.

예제 입력 1 

2 2 1 1
2 1
1 2

예제 출력 1 

2

예제 입력 2 

3 3 2 1
2 1 0
1 0 1
2 1 2

예제 출력 2 

2

예제 입력 3 

4 3 1 1
0 2 0
2 1 2
0 1 0
1 1 1

예제 출력 3 

1

예제 입력 4 

5 7 3 2
1 0 1 2 1 2 1
1 1 1 0 1 0 2
2 1 0 0 1 1 1
1 0 2 1 2 1 0
0 2 1 1 0 1 2

예제 출력 4 

5

예제 입력 5 

6 6 3 3
1 1 2 1 1 2
2 1 0 1 1 1
0 1 0 0 1 2
2 1 1 1 2 1
2 1 1 2 1 2
0 0 0 0 2 1

예제 출력 5 

9

예제 입력 6 

10 10 1 1
2 1 1 2 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1

예제 출력 6 

0

예제 입력 7 

13 20 2 5
1 1 0 1 0 0 1 0 0 2 0 1 0 0 1 2 0 2 1 1
1 1 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1
0 0 0 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0
1 2 0 0 0 1 0 0 1 1 0 1 1 0 0 1 1 0 1 0
0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1
1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0
0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0
0 1 0 0 1 1 0 1 0 0 0 0 1 0 1 0 0 1 0 0
0 0 2 0 0 0 0 0 2 1 0 1 0 0 0 0 0 0 0 0
1 1 0 0 0 1 0 2 1 0 0 0 1 1 0 0 0 0 0 0
0 0 0 0 1 1 0 0 1 0 0 0 1 1 2 1 0 1 0 1
0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0

예제 출력 7 

1

예제 입력 8 

13 15 4 3
1 0 1 1 0 0 0 0 2 0 0 0 2 0 1
0 1 1 0 1 0 1 0 1 1 0 1 1 1 0
1 1 2 0 0 0 1 0 0 1 0 0 1 1 1
0 1 2 0 1 1 0 1 0 0 1 0 1 1 1
1 1 1 0 1 0 0 2 0 1 2 1 0 0 0
1 0 1 0 1 1 0 1 2 1 1 1 1 1 2
1 1 1 1 1 1 1 1 0 1 1 0 1 1 0
2 1 0 1 0 0 0 0 0 1 0 1 0 1 0
0 1 0 0 0 0 1 0 1 0 1 1 1 1 1
1 1 1 0 1 1 0 1 0 0 0 1 0 0 0
1 1 0 1 0 0 0 0 1 1 0 1 0 1 0
1 0 0 0 0 0 1 1 1 1 0 0 0 1 0
0 1 1 1 0 0 0 1 1 1 0 0 1 1 0

예제 출력 8 

4

예제 입력 9 

16 13 3 3
2 1 1 1 0 0 0 0 0 1 1 0 0
1 0 2 0 0 0 0 0 0 2 0 1 1
0 1 0 1 0 1 0 1 0 2 0 1 0
0 0 0 1 0 2 1 0 0 0 0 1 1
0 0 0 0 2 1 1 0 0 0 0 1 0
0 1 0 0 0 1 2 0 1 0 0 0 0
1 1 0 0 0 0 1 0 0 1 0 0 0
0 0 1 0 0 0 0 1 0 0 1 0 0
0 0 0 1 2 0 0 0 0 1 1 0 0
0 0 1 1 1 0 0 0 1 0 1 0 0
0 0 2 0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 1 0 0 0 0 1 1
0 0 0 0 0 0 1 0 0 1 1 0 0
0 0 0 1 1 0 1 2 0 1 0 0 1
1 1 0 0 1 0 0 1 0 0 0 0 1

예제 출력 9 

2

예제 입력 10 

13 17 2 4
1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 0
1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1
1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 2 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1
1 1 1 1 1 1 1 2 1 1 1 1 1 1 0 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 1 1 1 2 1 1 1 1 2 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1

예제 출력 10 

26

 

⭕ CODE

from collections import deque
from itertools import combinations

# 4방향
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def bfs(new, all, green):
    q = deque()
    # 초를 세기 위한 cnt
    cnt = 0
    # 꽃을 피울 수 있는 maxcount
    maxcount = 0
    
    # 모든 가능한 조합 x,y좌표에서
    for x, y in all:
    	# x,y좌표가 green 즉 녹생 배양액에 있다면
        if (x, y) in green:
            # x,y는 좌표
            # 1은 녹색
            # 0은 초
            q.append((x, y, 1, 0))
            # 녹색은 3으로 변경하고 녹색 방문처리
            new[x][y] = 3
            visitedgreen[x][y][0] = 1
        # x,y좌표가 녹색에 없다면 빨간색 배양액이다.
        else:
            # 빨간색은 -1로 저장
            q.append((x, y, -1, 0))
            # 4로 변경하고 빨간색에 방문처리
            new[x][y] = 4
            visitedred[x][y][0] = 1

    while q:

        x, y, color, count = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 격자안에 존재하고
            if 0 <= nx < n and 0 <= ny < m:
                # 색상이 녹색이고 다음 진행칸이 이동가능(2or1)하고 녹색에 방문한적이 없고
                # 동시에 빨간색에 방문한적이 없다면
                if color == 1 and (new[nx][ny] == 2 or new[nx][ny] == 1) and visitedgreen[nx][ny][0] == 0 and visitedred[nx][ny][0] == 0:
                    # q에 담아주고
                    # 다음 진행할칸 녹색에 방문처리하고 1초 증가
                    q.append((nx, ny, color, count + 1))
                    visitedgreen[nx][ny][0] = 1
                    visitedgreen[nx][ny][1] = count + 1
                    
                # 색상이 녹색이고 다음 진행칸이 이동가능(2or1)하고 녹색에 방문한적이 없지만
                # 빨간색 칸에 방문한적이 있고 그 시간이 다음번 초에 방문한다면
                # 동시에 만나는 경우이다!!! -> 꽃을 피운다
                if color == 1 and (new[nx][ny] == 2 or new[nx][ny] == 1) and visitedgreen[nx][ny][0] == 0 and visitedred[nx][ny][0] == 1 and visitedred[nx][ny][1] == count + 1:
                    # 그럼 빨간색쪽에서 q에 담았을테니
                    # 만약 q에 nx,ny : 다음칸 -color 는 반대 색 이 존재한다면
                    if (nx, ny, -color, count + 1) in q:
                    	# q에서 삭제해주고
                        # 꽃을 피울 수 있는 개수 1 증가
                        q.remove((nx, ny, -color, count + 1))
                        maxcount += 1
                        
                # 빨간색 배양액의 경우도 녹색 배양액과 마찬가지로 처리해준다.
                if color == -1 and (new[nx][ny] == 2 or new[nx][ny] == 1) and visitedred[nx][ny][0] == 0 and visitedgreen[nx][ny][0] == 0:
                    visitedred[nx][ny][0] = 1
                    visitedred[nx][ny][1] = count + 1
                    q.append((nx, ny, color, count + 1))
                if color == -1 and (new[nx][ny] == 2 or new[nx][ny] == 1) and visitedred[nx][ny][0] == 0 and visitedgreen[nx][ny][0] == 1 and visitedgreen[nx][ny][1] == count + 1:
                    if (nx, ny, -color, count + 1) in q:
                        q.remove((nx, ny, -color, count + 1))
                        maxcount +=1
    # 최대 꽃 피울 수 있는 수 리턴
    return maxcount


n, m, g, r = map(int, input().split())

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

# 배양액 가능한 모든 좌표 담기 위한 possible
possible = []
for i in range(n):
    for j in range(m):
        if arr[i][j] == 2:
            possible.append((i, j))

# 초록 빨강 합 개수만큼의 뿌릴 수 있는 좌표의 모든 조합
allp = list(combinations(possible, g + r))

result = 0

# all은 각각의 조합들이다
for all in allp:
    # all은 가능한 배양액 땅(초록과 빨강 더한거)
    # arr 복사
    new = [a[:] for a in arr]
    # green은 모두 가능한거에서 녹색 개수 조합
    for green in list(combinations(all, g)):
    	# 녹색과 빨간색 배양액의 방문처리를 위한 visited생성
        # 여기서 visited[x][y][0]은 x,y좌표에 방문했는지 안했는지 0 or 1
        # visited[x][y][1]은 x,y좌표에 몇초에 들어갔는지 확인하기 위해
        visitedgreen = [[[0, 0] for _ in range(m)] for _ in range(n)]
        visitedred = [[[0, 0] for _ in range(m)] for _ in range(n)]

        # bfs(new, all, green)
        # 피울 수 있는 꽃의 최대 개수
        result = max(result, bfs(new, all, green))

print(result)

✏️ Comment

우선 가능한 모든 배양액을 뿌릴 수 있는 조합을 생각하고 녹색의 조합을 만들어서 거기서 빨간색 조합을 찾아서 모두 q에 담아주었다. 그리고 방문처리도 계속 초기화해주고 arr배열도 계속 초기화하도록 복사하여 만들어 주었다.

꽃을 피우는거는 같은 초에 서로 다른 배양액이 동시에 도착한다고 생각하고 문제에 집중하였다. 그래서 visited배열에 초를 판별하도록 만들어 주었고 다음에 갈 곳이 다른색상에서 다음초에 도착한다면 동시에 도착하므로 1개 증가시키도록 그리고 이미 다른색에서 다음단계가 q에 들어가있을 것이므로 그 부분을 삭제하도록 만들어주었다.

 

  • 다른 사람들의 문제 풀이에 비해서 시간이 많이 느리다. 시간을 줄이는 방법에 대해서 연구해보자

'알고리즘 > 백준' 카테고리의 다른 글

[BOJ 3019 🥈1] 테트리스 (Python)  (0) 2023.09.30
[BOJ 2164 🥈4] 카드 2 (Python)  (0) 2023.09.25
[BOJ 13904 🥇3] 과제 (Python)  (0) 2023.09.23
[BOJ 24390🥈1] 또 전자레인지야? (Python)  (0) 2023.09.22
[BOJ 1781🥇2] 컵라면 (Python)  (0) 2023.09.22
'알고리즘/백준' Related Articles more