Q16. 백준 14502 연구소

띠리링구 2022. 2. 7. 22:36

백준 파이썬 시간초과 관련 나노팁

전부터 백준 문제 풀면서 이상함을 느꼈는데, 알고리즘은 맞는데 자꾸 시간초과가 뜨는 현상. 즉, 풀이는 분명히 맞는데 시간초과가 뜨는 현상이다. 기본적으로 백준 서버가 좀 느린 것 같고 잘은 모르겠지만 언어별 속도차이를 고려하지 않고 채점하는 것 같다..아마? 하긴 제한 시간이 몇 초라고 딱 정해져있으니 그럴 수는 있지만 조금 언어별 시간제한을 다르게 해야되는게 아닌가 생각되는 부분이다.

tip

1. Python3 말고 PyPy3로 하자. 호환된다.

2. 백준에서 파이썬으로 문제를 풀 때는 사소한 부분이라도 optimization을 적용해야 한다. 코드가 빠르게 실행될 수 있게 하는 잡기술을 최대한 많이 알고 활용해야된다.

풀이 방법

상수 조건을 잘 보면 맵이 꽤 작음을 알 수 있다. 그리고 벽을 3개 세워야된다는 특이한 조건. 맵이 최대크기여도 64개의 칸이 존재하고 64개의 칸이 다 비었다 해도 3개의 벽을 일일이 세워볼 수 있다. (완전탐색, backtracking)

1. 벽을 3개 세운다.

2. 바이러스를 전파시켜본다.

3. 빈칸의 수를 세고 정답값이랑 비교해서 정답값을 업데이트한다.

한줄요약을 해볼까

1. 노가다

전체코드

maprow, mapcol = map(int,input().split())
labmap = []
temp = [[0]*mapcol for _ in range(maprow)]
for _ in range(maprow):
    labmap.append(list(map(int,input().split())))
maxsafe = 0

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

def printmap(labmap):
    for i in range(len(labmap)):
        print(labmap[i])
    print()

def spread(i, j):
    for k in range(4):
        newrow = i+dx[k]
        newcol = j+dy[k]

        if newrow>=0 and newrow<maprow and newcol>=0 and newcol<mapcol and temp[newrow][newcol]==0:
            temp[newrow][newcol] = 2
            spread(newrow,newcol)

def virus():
    for i in range(maprow):
        for j in range(mapcol):
            temp[i][j] = labmap[i][j]

    for i in range(maprow):
        for j in range(mapcol):
            if temp[i][j] == 2:
                spread(i,j)

    # print("before")
    # printmap(labmap)
    # print("after")
    # printmap(temp)

    count = 0
    for i in range(maprow):
        for j in range(mapcol):
            if temp[i][j] == 0:
                count += 1

    return count

def everycase(count):
    global labmap,maxsafe

    if count == 3:
        safe_zone = virus()
        maxsafe = max(maxsafe,safe_zone)
        return

    for i in range(maprow):
        for j in range(mapcol):
            if labmap[i][j] == 0:
                labmap[i][j] = 1
                everycase(count+1)
                labmap[i][j] = 0

everycase(0)
print(maxsafe)

코드 설명

인풋 받는 부분 및 초기화

중요한 부분은 굵은 글씨 처리했다

maprow, mapcol = map(int,input().split())
labmap = []

temp = [[0]*mapcol for _ in range(maprow)]

#원본 맵을 손상시키지 않고 바이러스를 전파시켜보기 위해

#만든 temp 2차원 리스트. 맵을 복제해놓고 바이러스를 전파시켜볼거다.

for _ in range(maprow):
labmap.append(list(map(int,input().split())))
maxsafe = 0 #정답값

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

#바이러스를 상하좌우로 전파시키기 위해 만든 dx,dy 변수값이다.

#2차원 배열 관련 문제에서 요긴하게 쓰이는 잡기술

#아래 굵은글씨로 어떻게 쓰는지 표시해뒀다

#디버깅을 위해 맵 출력할 때 쓰던 함수다. 실제 문제 제출시엔 안쓴다. 신경 안써도 된다.
def printmap(labmap):
    for i in range(len(labmap)):
        print(labmap[i])
    print()

서브 로직

바이러스 전파시키는 부분

def spread(i, j): # 맵[i][j]에 바이러스가 있을 때 호출된다. 상하좌우로 전파시킨다.
    for k in range(4):
        newrow = i+dx[k]
        newcol = j+dy[k]

        if newrow>=0 and newrow<maprow and newcol>=0 and newcol<mapcol and temp[newrow][newcol]==0:
            temp[newrow][newcol] = 2
            spread(newrow,newcol) #재귀호출~

def virus(): #온 맵의 바이러스를 다 찾아서 spread(전파)시킨다.

#temp에 맵 복제
    for i in range(maprow):
        for j in range(mapcol):
            temp[i][j] = labmap[i][j]

    for i in range(maprow):
        for j in range(mapcol):
            if temp[i][j] == 2:
                spread(i,j)

#바이러스 찾아서 전파시키기

# 디버깅의 흔적..
    # print("before")
    # printmap(labmap)
    # print("after")
    # printmap(temp)

#빈 칸의 수를 센다 (안전영역)
    count = 0
    for i in range(maprow):
        for j in range(mapcol):
            if temp[i][j] == 0:
                count += 1

    return count

메인로직

벽3개 세워보고 답을 찾아가는 부분

def everycase(count):
    global labmap,maxsafe

    if count == 3: # 벽 3개를 설치했으면
        safe_zone = virus() #바이러스를 퍼트려서 안전영역을 계산하고
        maxsafe = max(maxsafe,safe_zone) #정답값을 업뎃한다
        return

    for i in range(maprow):
        for j in range(mapcol):
            if labmap[i][j] == 0:
                labmap[i][j] = 1 #벽을 세워보기도 해보고
                everycase(count+1) #(호출)
                labmap[i][j] = 0 #벽을 안세우기도 해보고..

everycase(0)
print(maxsafe)