BOJ 14502. [Gold4] 연구소

[hojongs]

Problem link

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

Problem abstraction

문제의 핵심을 요약한다. 체계적인 문제 접근을 위해, 문제를 추상화한다

적합한 자료구조를 생각한다

Design(Plan) algorithm

# 1

문제 페이지 참고

---
# 2

---
# 3

Algorithm idea

추상화한 문제 이해를 기반으로 알고리즘의 대략적인 구현 계획을 서술한다

brute-force

Pseudo-code

idea를 수도 코드로 작성해본다

주석 참고

Validate algorithm

알고리즘의 유효 여부를 구현 전에 검증한다

예제 입력을 수도 코드로 계산해보고, 놓친 알고리즘 오류가 있는지 확인한다

예제 테스트 중 검증 -> 중간 loop 조건을 잘못 입력함 -> 디버깅 출력으로 찾음

Impl

import sys

readl = sys.stdin.readline


def f():
    n,m = [int(i) for i in readl().rstrip().split()]
    rows = [[i for i in readl().split()] for _ in range(n)]
    # Count the number of zeros
    zero_cnt = 0
    # check virus pos
    virus_pos_list = []
    for ri in range(n):
        row = rows[ri]
        for ci in range(m):
            col = row[ci]
            if col == '0':
                zero_cnt += 1
            elif col == '2':
                virus_pos_list.append([ri, ci])
    # print(zero_cnt, virus_pos_list)
    max_zero = 0
    # 벽 3개 세우기
    # traverse rows (0,0)
    for ri in range(0, n):
        row = rows[ri]
        # traverse cols
        for ci in range(0, m):
            # if curr is 0: set wall & traverse remaining and set wall (twice)
            if row[ci] != '0':
                continue
            # set wall (0)
            # print('set wall (0)')
            row[ci] = '1'
            # traverse rows (from ri,ci+1)
            for ri2 in range(ri, n):
                row2 = rows[ri2]
                for ci2 in range(0, m):
                    # for ci2 in range(ci+1, m) -> correct only if first iteration
                    # fix it to for ci2 in range(0, m)
                    if ri2 == ri and ci2 <= ci:
                        continue
                    if row2[ci2] != '0':
                        continue
                    # set wall (1)
                    # print('set wall (1)')
                    row2[ci2] = '1'
                    # traverse rows (from ri2,ci2+1)
                    for ri3 in range(ri2, n):
                        row3 = rows[ri3]
                        for ci3 in range(0, m):
                            if ri3 == ri2 and ci3 <= ci2:
                                continue
                            if row3[ci3] != '0':
                                continue
                            # set wall (2)
                            # print('set wall (2)')
                            row3[ci3] = '1'
                            # once set 3 walls, spread virus (DFS)
                            stack = virus_pos_list.copy()
                            # stack = [pos of 2s]
                            visited = [[False for _ in range(m)] for _ in range(n)]
                            virus_cnt = 0
                            # while stack: stack.pop() & count visit
                            while stack:
                                rr,cc = stack.pop()
                                if visited[rr][cc] or rows[rr][cc] == '1':
                                    continue
                                # 0,1 / 1,0 / 3,5
                                visited[rr][cc] = True
                                virus_cnt += 1
                                for rr2, cc2 in [
                                    [rr-1, cc],
                                    [rr+1, cc],
                                    [rr, cc-1],
                                    [rr, cc+1],
                                ]:
                                    if 0 <= rr2 < n and 0 <= cc2 < m and rows[rr2][cc2] != '1' and not visited[rr2][cc2]:
                                        stack.append([rr2, cc2])
                            # max_zero = max(max_zero, curr_zero)
                            # 3 is new wall
                            curr_zero_cnt = zero_cnt - 3 - virus_cnt + len(virus_pos_list)
                            # print(ri, ci)
                            # print(ri2, ci2)
                            # print(ri3, ci3)
                            # print(virus_cnt, curr_zero_cnt)
                            # input()
                            max_zero = max(max_zero, curr_zero_cnt)
                            # reset wall (2)
                            row3[ci3] = '0'
                    # reset wall (1)
                    row2[ci2] = '0'
            # reset wall (0)
            row[ci] = '0'
    print(max_zero)


f()

Self-feedback

구조적 접근: 문제를 추상화하여 구조적으로 접근했는가?

가장 무식한 방법도 고려해라.

무식한 방법은 코드가 복잡하지만 구현은 할 수 있어야 한다

중간 loop 조건을 잘못 줬었음. -> loop 돌아야 할 영역들을 이미지로 생각했으면 미리 알았으려나

사고력: 알고리즘을 완전히 이해했는가? (충분한 사고력을 가졌는가?)

구현력: 알고리즘을 신속, 정확하게 구현했는가?

[hojongs]

stack?