14502: 연구소

ewillwin·2023년 4월 8일
0

Problem Solving (BOJ)

목록 보기
12/230

tmp = list(map(int, input().split(' ')))
N = tmp[0]; M = tmp[1]

board = []
for _ in range(N):
    board.append(list(map(int, input().split(' '))))

dx = [-1, 1, 0, 0] #상하좌우
dy = [0, 0, -1, 1] #상하좌우

def combination(arr, n):
    result = []
    if n > len(arr):
        return result
    if n == 1:
        for i in arr:
            result.append([i])
    elif n > 1:
        for i in range(len(arr) - n + 1):
            for j in combination(arr[i+1:], n-1):
                result.append([arr[i]] + j)
    return result

def cpy(list):
    tmp = [[0] * M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            tmp[i][j] = list[i][j]
    return tmp

def save(wall):
    bbb = cpy(board)
    for i in range(3):
        bbb[wall[i][0]][wall[i][1]] = 1
        
    while True:
        cnt = 0
        for i in range(N):
            for j in range(M):
                if bbb[i][j] == 2:
                    for d in range(4):
                        x = i + dx[d]; y = j + dy[d]
                        if x >= 0 and x < N and y >= 0 and y < M:
                            if bbb[x][y] == 0:
                                bbb[x][y] = 2; cnt += 1
        if cnt == 0:
            break

    zero_cnt = 0
    for i in range(N):
        for j in range(M):
            if bbb[i][j] == 0:
                zero_cnt += 1
    return zero_cnt

walls = []
for i in range(N):
    for j in range(M):
        if board[i][j] == 0:
            walls.append((i, j))

all_wall = combination(walls, 3)
answer = 0
for i in range(len(all_wall)):
    local_answer = save(all_wall[i])
    answer = max(answer, local_answer)
print(answer)
  • brute force로 해결
  • 벽을 세울 수 있는 모든 좌표를 walls에 저장함
  • recursion을 사용한 combination 함수를 통해 walls에서 3개의 tuple을 선택하는 조합을 all_wall에 저장함
  • all_wall에 있는 원소들을 모두 순회하면서 가장 save_cnt가 큰 경우를 출력해줌
profile
💼 Software Engineer @ LG Electronics | 🎓 SungKyunKwan Univ. CSE

0개의 댓글