BrianaAI

안녕하세요.

브리아나입니다.

반례때문에 한참을 풀었네요..휴..(질문게시판 보고 알았습니다)

문제.

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

풀이.

N, M = map(int, input().split())
arr = []
virus = []
for i in range(N):
    arr.append(list(map(int, input().split())))
    for j in range(N):
        if arr[i][j] == 2: # 바이러스
            virus.append((i, j))
            arr[i][j] = 0 # 미리 바이러스 가능공간 0으로 없애버리기
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

def solve(tlst):
    # make a wall
    w = [[0] * N for _ in range(N)]

    # [1] virus 넣어
    q = []
    for tx, ty in tlst:
        w[tx][ty] = 1
        q.append((tx, ty))

    m = 0
    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<N and w[nx][ny] == 0 and arr[nx][ny] == 0:
                w[nx][ny] = w[cx][cy]+1
                q.append((nx, ny))
                m = max(m, w[nx][ny])

    for i in range(N):
        for j in range(N):
            if w[i][j] == 0 and arr[i][j] == 0: # 그냥 길인데, 방문안한곳이 있다면
                return float("inf")
    # print("m: ", m-1, tlst)
    if m>0:
        return m-1
    return m


ans = float("inf")

def bfs(n, lst):
    global ans
    if len(lst) == M:
        ans = min(ans, solve(lst))
        return

    for i in range(n, len(virus)):
        if v[i] == 0:
            v[i] = 1
            bfs(i+1, lst+[virus[i]])
            v[i] = 0
    return

v = [0]*(len(virus))
bfs(0, [])

if ans == float("inf"):
    ans = -1
print(ans)

반례. 놓자마자 퍼짐. 그래서 저의 경우 0이 아닌 -1이 출력 되어서

5 2
1 1 1 1 1
1 1 2 1 1
1 1 2 1 1
1 1 1 1 1
1 1 1 1 1

if m>0:

return m-1

return m

이 문장을 넣어줬어요...휴...

안녕하세요.

브리아나입니다.

오늘은 백트래킹 말고,

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

그래도 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, [])

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

안녕하세요.

브라아나입니다.

정답코드.

N = int(input())
S = [list(map(int, input().split())) for i in range(N)]
tmp = [0] + [i + 1 for i in range(N)]  # 1,2,3,4
ans = 999999
test_list = []
v = [0] * (N + 1)


def DFS(s, lst):
  global test_list
  if len(lst) == int(N / 2):
    test_list.append(lst)
    return
  for i in range(s, N + 1):
    if v[i] == 0:
      v[i] = 1
      DFS(i + 1, lst + [tmp[i]])
      v[i] = 0


# [1] 조합 만들기 - 2/N 개 만큼
DFS(1, [])

# [2] 점수 계산하기
for i in range(int(len(test_list) / 2)):
  start_ability, link_ability = 0, 0
  for j in range(len(test_list[0]) - 1):
    for k in range(j + 1, len(test_list[0])):
      si, sj = test_list[i][j], test_list[i][k]
      link = test_list[int(len(test_list)) - 1 - i]
      li, lj = link[j], link[k]
      si, sj, li, lj = si - 1, sj - 1, li - 1, lj - 1
      start_ability += S[si][sj] + S[sj][si]
      link_ability += S[li][lj] + S[lj][li]
  difference = abs(start_ability - link_ability)
  # print("result: ", test_list[i], difference)
  if ans > difference:
    ans = difference

print(ans)

풀이.