BrianaAI

안녕하세요.

브리아나입니다.

오늘은 백트래킹 말고,

시간 더 단축시킬 수 있는 경우를 풀어보겠습니다.

그래도 3개라는 숫자가 주어지니까 가능한 버전입니다.

문제.

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

풀이.

N, M = map(int, input().split())
arr = []
path = []
virus = []
for i in range(N):
    arr.append(list(map(int, input().split())))
    for j in range(M):
        if arr[i][j] == 0:
            path.append((i, j))
        elif arr[i][j] == 2:
            virus.append((i, j))

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

def bfs(tlst):
    # [1] make wall 3 times
    for tx, ty in tlst:
        arr[tx][ty] = 1

    # [2] initialize virus info
    q = []
    w = [[0]*M for _ in range(N)]
    for vx, vy in virus:
        w[vx][vy] = 1
        q.append((vx, vy))
    chance = cnt-3

    while q:
        cx, cy = q.pop(0)
        for i in range(4):
            nx, ny = cx+dx[i], cy+dy[i]
            if 0<=nx<N and 0<=ny<M and w[nx][ny] == 0 and arr[nx][ny] == 0:
                w[nx][ny] = 1
                q.append((nx, ny))
                chance-=1

    # reset
    for tx, ty in tlst:
        arr[tx][ty] = 0

    return chance


cnt = len(path)
ans = 0

for i in range(cnt-2):
    for j in range(i+1, cnt-1):
        for k in range(j+1, cnt):
            ans = max(ans, bfs([path[i], path[j], path[k]]))
print(ans)

참고하세요 ~~

안녕하세요.

백트래킹을 공부하고 싶은 사람 있으면

N과 M 시리즈부터 공부를 해야해요.

https://www.acmicpc.net/workbook/view/2052

여기 들어가면 시리즈가 있습니다.

1번부터 12번까지의 저의 풀이 남기겠습니다. :) 화잇팅

#1.

N, M = map(int, input().split())
tmp = [i for i in range(N+1)]
def DF(lst):
    if len(lst)==M:
        print(" ".join(map(str, lst)))
        return
    for i in range(1, N+1):
        DF(lst+[tmp[i]])
DF([])

#2.

N, M = map(int, input().split())
tmp = [i for i in range(N+1)]
v = [0]*(N+1)

def DF(lst):
    if len(lst) == M:
        print(" ".join(map(str, lst)))
        return
    for i in range(1, N+1):
        if v[i] == 0:
            v[i] = 1
            DF(lst+[tmp[i]])
            v[i] = 0
DF([])

#3.

N, M = map(int, input().split())
tmp = [i for i in range(N+1)]
v = [0]*(N+1)

def DF(s, lst):
    if len(lst) == M:
        print(" ".join(map(str, lst)))
        return

    for i in range(s, N+1):
        if v[i] == 0:
            v[i] = 1
            DF(i, lst+[tmp[i]])
            v[i] = 0
DF(1, [])

#4.

N, M = map(int, input().split())
tmp = [i for i in range(N+1)]

def DF(s, lst):
    if len(lst) == M:
        print(" ".join(map(str, lst)))
        return

    for i in range(s, N+1):
        DF(i, lst+[tmp[i]])

DF(1, [])

#5.

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
v = [0]*(N+1)

def DF(lst):
    if len(lst) == M:
        print(" ".join(map(str, lst)))
        return

    for idx, i in enumerate(arr):
        if v[idx] == 0:
            v[idx] = 1
            DF(lst+[arr[idx]])
            v[idx] = 0
DF([])

#6.

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
v = [0]*(N)
def DF(s, lst):
    if len(lst) == M:
        print(" ".join(map(str, lst)))
        return
    for i in range(s, len(arr)):
        if v[i] == 0:
            v[i] = 1
            DF(i, lst+[arr[i]])
            v[i] = 0
DF(0, [])

#7.

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
def DF(lst):
    if len(lst) == M:
        print(" ".join(map(str, lst)))
        return

    for i in range(len(arr)):
        DF(lst+[arr[i]])
DF([])

#8.

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
def DF(s, lst):
    if len(lst) == M:
        print(" ".join(map(str, lst)))
        return
    for i in range(s, len(arr)):
        DF(i, lst+[arr[i]])
DF(0, [])

# 9.

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
ll = []
v = [0]*N
def DF(lst):
    if len(lst) == M:
        if lst not in ll:
            print(" ".join(map(str, lst)))
            ll.append(lst)
        return
    for i in range(len(arr)):
        if v[i] == 0:
            v[i] = 1
            DF(lst+[arr[i]])
            v[i] = 0
DF([])

#10.

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
v = [0]*N
ll = []

def DF(s, lst):
    if len(lst) == M:
        if lst not in ll:
            ll.append(lst)
            print(" ".join(map(str, lst)))
        return
    for i in range(s, len(arr)):
        if v[i] == 0:
            v[i] = 1
            DF(i, lst+[arr[i]])
            v[i] = 0
DF(0, [])

# 11.

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
ll = []

def DF(lst):
    if len(lst) == M:
        if lst not in ll:
            print(" ".join(map(str, lst)))
            ll.append(lst)
        return
    for i in range(len(arr)):
        DF(lst+[arr[i]])
DF([])

#12.

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
ll = []
def DF(s, lst):
    if len(lst) == M:
        if lst not in ll:
            ll.append(lst)
            print(" ".join(map(str, lst)))
        return
    for i in range(s, len(arr)):
        DF(i, lst+[arr[i]])
DF(0, [])

1. PyInstaller란

파이썬은 소스 코드 베이스라 실행 파일로 만들어줘야해요. 이때, PyInstaller를 사용하면 사용이 가능합니다.

파이썬 코드를 실행파일형태로 패키징해서 별도의 인터프리터 없이도 해당 프로그램을 실행할 수 있게 해줍니다.

2. 가상환경 구축하기

먼저, 가상환경을 먼저 구축하는 이유는 우리가 배포하려고 하는 가상환경에 바로 설치하면 여러 라이브러리들의 충돌이 일어납니다. 흔한 예로 Pathlib ..^_^ conda로 지우라는 에러가 나오는데 후기를 읽어보면 엄청나게 복잡한 과정이라고하네요. 그래서 그냥 step by step으로 필요한거 하나씩 설치하는 방법을 택했어요...

conda create -n pyinstaller python=3.8
conda activate pyinstaller
# (pyinstaller) 괄호바뀜
pip install pyinstaller
pip install -r requirements.txt # 본인들이 필요한 라이브러리 여기로 넣고 한 번에 설치 고고

3. 사용방법

pyinstaller filename.py

이렇게만 수행하면 build, dist 폴더 2개, .spec 파일 1개가 생성됩니다. 

4. 여러옵션

• --onefile: 1개의 파일로 만들기
• -w / --windowed : 콘솔창 출력 안되게 하기
• -n: 이름 정해주기, (안정해주면 파일이름)
• --icon=icon.ico : 아이콘 지정해주기
• -d: 디버그모드로 만들기

* 주의사항

- 해보면서 느낀건데, dist랑 build 폴더내에 삭제 안하고 계속 그냥 pyinstaller filename.py 하면 바뀌는게 없어요. 어쩐지 계속 같은 가상환경에 파일이 없다~ 에러 뜨더라구요. 제대로 할거면 build랑 dist 폴더 완전삭제하고 필요패키지 설치하고 다시 pyinstaller filename.py 수행하기.