(22 복습) 삼성 SW 역량 테스트 기출 문제 / 백준 / 17142번: 연구소 3

[sallyy1]

첫 풀이

• 80% 대 틀렸습니다.

# 활성 상태(상하좌우 복제됨), 비활성 상태
# 전체 바이러스 중 M개를 활성 상태로 변경하려고 함

##########
## 조합 함수
def combinations(array, r):
    for i in range(len(array)):
        if r == 1:
            yield [array[i]]

        else:
            for next in combinations(array[i+1:], r-1):
                yield [array[i]] + next
##########



from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


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

answer = -1 # 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간


candidates = []
for i in range(n):
    for j in range(n):
        if a[i][j] == 2:
            candidates.append((i, j))



all_cases = combinations(candidates, m)




for case in all_cases:
    # print(case)

    q = deque()
    check = [ [-1] * n for _ in range(n)]
    #### (이 문제에선 복사배열 안 써도 가) b = [row[:] for row in a] # a 배열의 복사배열을 미리 준비

    for x, y in case:
        q.append((x, y))
        check[x][y] = 0 # 활성 바이러스는 0초부터 시작


    # print(q)
    # for line in check:
    #     print(line)


    ## BFS 탐색
    while q:
        x, y = q.popleft()

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

            if 0<=nx<n and 0<=ny<n:
                if a[nx][ny] == 1 or check[nx][ny] == 0: # 벽이거나, 선택한 m개의 활성 바이러스라면
                    continue

                if a[nx][ny] == 2 and (nx, ny) not in case: # (주의)선택받지 못한 나머지 비활성 바이러스도 이미 바이러스이므로 -> 방문할 필요 없음 !
                    continue

                if check[nx][ny] == -1 or check[nx][ny] > (check[x][y]+1):
                    check[nx][ny] = (check[x][y]+1)
                    q.append((nx, ny))



    # print()
    # for line in check:
    #     print(line)

    # 정답 체크
    ok = True

    for i in range(n):
        for j in range(n):
            if a[i][j] == 0 and check[i][j] == -1: # 빈칸인데 바이러스가 끝까지 방문 못한 곳이 있다면, 실패 사례
                ok = False
                break

    if ok == True:
        result_time = max([max(row) for row in check])
        # print(result_time)

        if answer == -1 or answer > result_time:
            answer = result_time


print(answer)

정답

• 문제에서 요구한 건, "연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다."
• 모든 "빈칸"에 바이러스가 있게 되는 최소시간
• 즉, 마지막 단계에서 해당 combinations 케이스의 '최소 시간'을 계산할 때, '빈칸'에 대해서만 고려하면 됐는데 / 처음에는 '비활성 바이러스' 칸까지 고려해서 반례가 생겼었음
• BFS 부분의 조건은 고쳐줄 필요 없었고, 최소 시간 계산하는 부분의 조건 고쳐주니 통과

# 활성 상태(상하좌우 복제됨), 비활성 상태
# 전체 바이러스 중 M개를 활성 상태로 변경하려고 함

##########
## 조합 함수
def combinations(array, r):
    for i in range(len(array)):
        if r == 1:
            yield [array[i]]

        else:
            for next in combinations(array[i+1:], r-1):
                yield [array[i]] + next
##########



from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


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

answer = -1 # 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간


candidates = []
for i in range(n):
    for j in range(n):
        if a[i][j] == 2:
            candidates.append((i, j))



all_cases = combinations(candidates, m)




for case in all_cases:
    # print(case)

    q = deque()
    check = [ [-1] * n for _ in range(n)]
    #### (이 문제에선 복사배열 안 써도 가) b = [row[:] for row in a] # a 배열의 복사배열을 미리 준비

    for x, y in case:
        q.append((x, y))
        check[x][y] = 0 # 활성 바이러스는 0초부터 시작


    # print(q)
    # for line in check:
    #     print(line)


    ## BFS 탐색
    while q:
        x, y = q.popleft()

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

            if 0<=nx<n and 0<=ny<n:
                if a[nx][ny] == 1 or check[nx][ny] == 0: # 벽이거나, 선택한 m개의 활성 바이러스라면
                    continue


                if check[nx][ny] == -1 or check[nx][ny] > (check[x][y]+1):
                    check[nx][ny] = (check[x][y]+1)
                    q.append((nx, ny))



    # print()
    # for line in check:
    #     print(line)


    # 정답 체크
    ok = True
    result_time = 0 ##

    for i in range(n):
        for j in range(n):
            if a[i][j] == 0:
                if check[i][j] == -1: # 빈칸인데 바이러스가 끝까지 방문 못한 곳이 있다면, 실패 사례
                    ok = False
                    break

                else: # 빈칸이고 바이러스가 방문한 곳이 있을 때만 -> 최소 시간 계산에 업데이트
                    result_time = max(result_time, check[i][j])


    if ok == True:
        ## 이렇게 풀면 틀림 =>
        ## 문제에서 요구하는 조건은 "모든 '빈칸'에 바이러스를 퍼뜨리는 최소시간을 구하라"
        ## 따라서, 비활성 바이러스를 활성 바이러스로 감염시킨 시간까지는 최소 시간 계산에 고려하지 않음 !
        # result_time = max([max(row) for row in check])
        # print(result_time)

        if answer == -1 or answer > result_time:
            answer = result_time


print(answer)