BrianaAI

안녕하세요.

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

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)

풀이.

문제.

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

풀이.

N, S = map(int, input().split())
data = list(map(int, input().split()))
tmp = [0] + [i for i in data]
answer = 0
def DFS(s, lst):
    global answer
    if sum(lst)==S and len(lst):
        answer+=1
    for i in range(s+1, N+1):
        DFS(i, lst+[tmp[i]])

DFS(0, [])
print(answer)

안녕하세요.

브리아나입니다.

오늘은 14503 백준 로봇청소기 문제를 풀어보겠습니다.

BFS(너비우선탐색, breadth-first-search)로 풀어보겠습니다.

문제링크.

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

문제 아이디어 정리하기.

1) 이슈가 될 수 있는 아이디어 정리하기

청소기 방향
cd = 0(북), 1(동), 2(남), 3(서) # cd: current direction
dx = [-1, 0, 1, 2]
dy = [0, 1, 0, -1]

청소기가 왼쪽 방향으로 회전한다.
현재 만약 서쪽이라면, 남->동->북->서 방향으로 회전
(현재 만약 3, 2->1->0->3 으로 회전)
IDEA: 보수를 더해주고 나머지 구하기 => (dr+3)%4
2-> 5%4 -> 1
1 -> 4%4 -> 0
0 -> 3%4 -> 3
3 -> 6%4 -> 2

2) 1번 항목부터 식을 세워보기.

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.

• 지도 = arr / 현재위치 (cx, cy) / 벽(1),청소x(0)이니까 청소하면(2)
• 청소 했는지 체크 count 변수

room_map[cx][cy] = 2
cnt+=1

2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
    바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
    바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.

• 후진: 방향 부호를 반전 시켜주면 됨.
  • bx = cx - dx[cd] (back_x = current_x - dx[current_direction]
  • if room_map[bx][by] != 1: # 벽 아니면 후진 가능
    • cx, cy = bx, by # 업데이트
    • 1번으로 돌아가야 하니까 순회(for) 멈추기: break
    • while문 빠져나갈 수 있게 (True -> False)

3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
    반시계 방향으로 90도 회전한다.
    바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
    1번으로 돌아간다.

• 왼쪽 방향부터 4방향 탐색 (다음 방향이니까 (nx, ny)) (이때, n은 next를 의미)
  • for: 빈곳(0) 있다? 2(청소) / 새로운 방향, 좌표 update
  • else: 빈곳(0) 없다? 후진 벽 아니라면? 후진 / 후진 벽이라면 종료

문제풀이.

1. 입력부, 출력부 작성하기

N, M = map(int, input().split())
cx, cy, cd = map(int, input().split())
room_map = [list(map(int, input().split())) for _ in range(N)]

def solution(cx, cy, cd):
	print("algorithm here")

print(solve(cx, cy, cd))

2. 전체 알고리즘 넣기

import sys
sys.stdin = open("input_14503.txt", "r")
# 북, 동, 남, 서 (반시계 90' 방향)
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

N, M = map(int, input().split())
cx, cy, cd = map(int, input().split()) # current_x, current_y, current_direction
room_map = [list(map(int, input().split())) for _ in range(N)]


def solution(cx, cy, cd):
    clean_count = 0

    while True:
        # 1) current room / no clean? / then, clean
        if room_map[cx][cy] == 0:
            room_map[cx][cy] = 2
            clean_count += 1
        con = True
        while con:
            for nd in ((cd+3)%4, (cd+2)%4, (cd+1)%4, cd): # condition access OK
                nx, ny = cx+dx[nd], cy+dy[nd]
                if room_map[nx][ny] == 0:
                    cx, cy, cd = nx, ny, nd
                    con = False
                    break # 청소 당첨되는 즉시 퇴장
            else: # no condition
                bx, by = cx-dx[cd], cy-dy[cd] # 후진
                if room_map[bx][by] != 1:
                    cx, cy = bx, by

                    break
                else:
                    return clean_count


print(solution(cx, cy, cd))

궁금한 사항 있으시면 질문 댓글로 주세요 :)