[BOJ 16988🥇3] Baaaaaaaaaduk2 (Easy)(Python)

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

16988번: Baaaaaaaaaduk2 (Easy)

문제

서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 주인 자리에서 쫓겨난지 오래이다. 그나마 다행인 것은 AI가 인간을 적대적으로 대하지 않고, 도리어 AI가 쌓아올린 눈부신 기술의 발전으로 모든 사람이 무제한적인 재화를 사용할 수 있게 되어 한 세기 전의 사람들이 바라던 돈 많은 백수와 같은 삶을 누릴 수 있게 됐다는 사실이다. 대다수의 인간들은 현재의 상황에 만족하고 더 이상 발전을 포기한 채 놀고 먹으면서 시간을 보내고 있지만 일부 인간들은 인류의 영광을 되찾기 위해 저항군을 조직해 AI에게 투쟁하고 있다.

저항군은 AI에게 승산이 있는 종목을 찾고 있다. 이러한 종목을 가지고 AI에게 승부를 걸어 전 인류에게 도전정신과 인간의 위대함을 증명하고 싶기 때문이다. 저항군의 지도부는 무려 12시간에 걸쳐 AI에게 승산이 있는 종목을 찾기 위한 회의를 진행했다. 회의에서 알고리즘 문제 풀이 대결, 가위불바위총번개악마용물공기보스펀지늑대나무사람뱀 게임, 캐치마인드, 알까기, 스타크래프트, 똥 피하기 게임, 딸기 2비트, 딸기수박당근참외메론 게임, 백일장, 사생 대회 등 다양한 아이디어가 나왔지만 단 0.01%라도 승산이 있어 보이는 종목은 하나도 없었다.

그렇게 모두가 낙담하던 중 누군가가 역사책을 뒤져 인간이 AI에게 승산이 있는 종목을 찾아냈다. 바로 정확히 100년 전에 있었던 이세돌과 알파고의 바둑 대결이었다. 물론 알파고는 그 이후로 발전을 거듭했기에 바둑에서의 승산은 없지만 바둑의 룰을 변형한 Baduk2라는 종목에서는 이세돌이 알파고에게 한 세트를 이긴 것과 같이 인간이 AI에게 승산이 있다고 판단했다.

Baduk2의 룰은 바둑과 거의 유사하지만 양 선수가 돌을 1개씩 번갈아 두는 것이 아니라 2개씩 둔다는 점이 다르다. 서술의 편의를 위해 상하좌우로 인접한 같은 색 돌의 집합을 그룹이라고 하자. 아래의 판에서는 흑의 그룹과 백의 그룹이 각각 3개씩 존재한다.

Baduk2에서는 일반적인 바둑과 동일하게 자신의 돌로 상대방의 그룹을 빈틈없이 에워싸면 갇힌 돌을 죽일 수 있다. 어느 그룹이 빈틈없이 에워싸였다는 것은 그 그룹 내에 빈 칸과 인접해있는 돌이 하나도 없다는 것과 동치이다.

그리고 Baduk2에서는 모든 비어있는 칸에 돌을 둘 수 있다. 설령 상대 돌로 둘러싸여 있어 스스로 잡히는 곳이라고 하더라도 상관이 없다. 아래와 같은 상황을 생각해보자.

두 빨간 칸 모두 백의 입장에서 착수할 경우 연결된 그룹이 흑돌로 둘러싸이게 되어 원래 바둑의 규칙에서는 백의 입장에서 스스로 잡히는 곳이지만 Baduk2에서는 이와 무관하게 백이 빨간 칸 두 곳에 착수해 8개의 흑돌이 들어있는 그룹의 돌을 죽일 수 있다.

저항군은 AI에게 Baduk2로 도전장을 내밀었고 AI는 의외로 순순히 도전을 받아들였다. 이제 저항군은 2116년 3월 9일, 인류의 자존심을 건 Baduk2 대결을 시작한다. 그리고 당신에게 인류의 승리를 돕기 위해 현재 판 위에서 돌 2개를 두어 상대 돌을 최대한 많이 죽이게끔 하는 프로그램을 작성하는 임무가 주어졌다. 인류의 명예를 걸고 현재 판이 주어질 때 돌 2개를 두어 죽일 수 있는 상대 돌의 최대 갯수를 구하는 프로그램을 작성하자.

입력

첫째 줄에 바둑판의 행의 갯수와 열의 갯수를 나타내는 N(3 ≤ N ≤ 20)과 M(3 ≤ M ≤ 20)이 한 칸의 빈칸을 사이에 두고 주어진다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0, 1, 2이다. 0은 빈 칸, 1은 나의 돌, 2는 상대의 돌을 의미한다. 빈 칸이 2개 이상 존재함과 현재 바둑판에서 양 플레이어 모두 상대방의 돌로 빈틈없이 에워싸인 그룹이 없음이 모두 보장된다.

출력

첫째 줄에 현재 판에서 돌 2개를 두어 죽일 수 있는 상대 돌의 최대 갯수를 출력한다.

예제 입력 1 복사

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

예제 출력 1 복사

1

예제 입력 2 복사

5 4
0 0 0 0
0 2 2 0
0 2 0 0
2 2 0 0
2 2 0 0

예제 출력 2 복사

0

예제 입력 3 복사

8 4
0 0 2 0
0 1 2 2
0 0 1 1
2 0 0 0
0 1 0 0
2 0 1 0
2 0 0 0
0 0 0 0

예제 출력 3 복사

3

예제 입력 4 복사

3 3
2 2 2
2 2 2
0 2 0

예제 출력 4 복사

7

예제 입력 5 복사

8 6
0 0 1 2 2 2
0 0 1 2 2 2
0 1 1 0 2 2
1 2 2 0 1 1
1 2 2 1 0 0
1 2 1 0 2 0
1 1 0 0 0 1
0 1 0 0 0 0

예제 출력 5 복사

13

예제 입력 6 복사

7 7
0 0 0 0 1 0 0
2 0 1 1 2 1 0
2 1 2 0 2 2 1
2 1 2 2 0 1 0
2 1 2 1 0 0 0
2 1 2 1 0 0 0
2 2 1 0 0 0 0

예제 출력 6 복사

8

예제 입력 7 복사

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

예제 출력 7 복사

10

 

⭕ CODE

from collections import deque
from itertools import combinations

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


def bfs(x, y):
    q = deque()
    q.append((x, y))
    visited[x][y] = 1
    while q:
        x, y = q.popleft()

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

            if 0 <= nx < n and 0 <= ny < m:
                # 상대바둑돌이고 방문한적 없다면
                if arr[nx][ny] == 2 and visited[nx][ny] == 0:
                    # 방문표시 및 큐에 담기
                    visited[nx][ny] = 1
                    q.append((nx, ny))
                # 주변에 비어있는 공간이 있다면
                # group리스트에 담아주기
                # group -> 0이 들어갈 수 있는 자리
                if arr[nx][ny] == 0:
                    group.append((nx, ny))


def newbfs(x, y):
    q = deque()
    q.append((x, y))
    visited[x][y] = 1
    # 상대돌 개수 세기 위한 twocount
    twocount = 0
    # 주변에 0이 존재하는지 체크하기 위한 flag
    flag = 0
    while q:
        x, y = q.popleft()
        # 상대돌 한개 증가
        twocount += 1

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

            if 0 <= nx < n and 0 <= ny < m:
                # 상대돌이고 방문한적없으면 방문처리하고 큐에 담기
                if arr[nx][ny] == 2 and visited[nx][ny] == 0:
                    visited[nx][ny] = 1
                    q.append((nx, ny))
                # 주변에 0이 존재하면 flag = 1
                if arr[nx][ny] == 0:
                    flag = 1

    return twocount, flag


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

# 0: 빈칸, 1: 내 돌, 2: 상대 돌
arr = [list(map(int, input().split())) for _ in range(n)]

# 결과값을 위한 result
result = 0

visited = [[0] * m for _ in range(n)]

# 0이 들어갈 수 있는 좌표들을 저장하기위한 리스트
possible = []

for i in range(n):
    for j in range(m):
        # 그룹별로 주변에 0이 몇개인지 세어주기 위해서
        # 만약 한 그룹에서 주변에 0이 3개 이상이라면 바둑돌 2개를 두어도 못잡으니까
        # possible리스트에 담지 않는다
        group = []
        # 상대 바둑돌 탐색
        if arr[i][j] == 2 and visited[i][j] == 0:
            bfs(i, j)
            # 그룹의 길이가 2이하인 애들만 possible리스트에 담아준다
            if len(set(group)) <= 2:
                possible += group
# 중복제거
possible = list(set(possible))

# 만약 바둑을 둘곳이 하나라면
if len(possible) == 1:
    # 그 좌표만 1로 바꾸어주고
    arr[possible[0][0]][possible[0][1]] = 1

    # 죽일 수 있는 돌의 합
    alltwo = 0

    visited = [[0] * m for _ in range(n)]
    for a in range(n):
        for b in range(m):
            # 상대돌 탐색
            if arr[a][b] == 2 and visited[a][b] == 0:
                # twocount : 2의 개수
                # flag : 주변에 0 이 존재하는지
                twocount, flag = newbfs(a, b)
                # 주변에 0이 존재하지 않는다면
                # 즉 상대돌을 죽일 수 있다면
                if flag != 1:
                    # 더해주자
                    alltwo += twocount
    # 더 큰값으로 갱신
    result = max(result, alltwo)
# 바둑을 둘 수 있는 곳이 여러곳이라면
else:
    # 모든 조합을 allpossible 리스트에 저장
    allpossible = list(combinations(possible, 2))

    for i in allpossible:

        # 가능한 위치를 내 돌로 변환
        arr[i[0][0]][i[0][1]] = 1
        arr[i[1][0]][i[1][1]] = 1

        alltwo = 0
        visited = [[0] * m for _ in range(n)]
        for a in range(n):
            for b in range(m):
                if arr[a][b] == 2 and visited[a][b] == 0:
                    twocount, flag = newbfs(a, b)
                    if flag != 1:
                        alltwo += twocount
        result = max(result, alltwo)

        # 내돌둔거 다시 초기화
        # 다른돌을 두어야하므로
        arr[i[0][0]][i[0][1]] = 0
        arr[i[1][0]][i[1][1]] = 0
print(result)

✏️ Comment

우선은 돌을 둘 수 있는 공간들만 따로 빼야겠다고 생각을 하여 2(상대돌)에 대해서 bfs를 돌아서 0(빈자리)인 좌표를 저장해주었다. 이 과정에서 그룹별로 주변에 0(빈자리)이 3개이상 존재한다면 2개의 돌로 죽일 수 없으므로 이런 경우는 possible리스트에 넣지 않았다. 그리고 possible에 대해서 조합을 만들어서 모든경우를 살피려고 했는데

3 3
1 0 1
1 1 1
1 0 2
이런경우에 possible에는 [(2,1)]만 들어가기 때문에 possible리스트의 길이가 1인 경우는 따로 빼주어서 처리해주었다.

조합으로 만들어서 bfs를 다시 돌리며 주변에 2의 개수를 판별할 때

# 상대돌이고 방문한적없으면 방문처리하고 큐에 담기
if arr[nx][ny] == 2 and visited[nx][ny] == 0:
    visited[nx][ny] = 1
    q.append((nx, ny))
# 주변에 0이 존재하면 flag = 1
if arr[nx][ny] == 0:
    twocount = 0
    break​

이런식으로 작성하여서 원래 2에 대해서 모두 방문처리를 하였어야하는데 잘못된 break의 사용으로 정답이 다르게 나왔다. 이 경우에는 위 코드처럼 flag를 따로 설정해주어서 해결하였다.

지금 다시보니 bfs함수와 newbfs함수를 동시에 사용할 수 있을것같다. 이런부분도 잘 생각하자

 

• 최악의 상황을 항상 생각하여 예외처리를 해야하는데 아직 그 부분이 많이 미숙하다. 조금만 더 깊게 생각하고 항상 의심하는 습관을 기르자