14712_넴모넴모 (Easy) (Python)

0. 출처

• 유형 : 백트래킹 (silver 1)
• 링크 : 14712번: 넴모넴모 (Easy)

1. 기록

• 22/04/04 (월)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
2 2

- 예제 출력 1 -
15

- 예제 입력 2 -
2 3

- 예제 출력 2 -
57

- 예제 입력 3 -
3 5

- 예제 출력 3 -
22077

(3) 코드

import sys

n, m = map(int, sys.stdin.readline().split())
graph = [[0] * (m + 1) for _ in range(n + 1)]
answer = 0


def dfs(cnt):
    global answer
    if cnt == n * m:
        answer += 1
        return

    x = cnt // m + 1
    y = cnt % m + 1

    dfs(cnt + 1)
    if graph[x - 1][y] == 0 or graph[x][y - 1] == 0 or graph[x - 1][y - 1] == 0:
        graph[x][y] = 1
        dfs(cnt + 1)
        graph[x][y] = 0


dfs(0)
print(answer)

(4) 정리

문제 가지수가 왜 저렇게 나오나 해서 직접 그려보았다.
넴모넴모가 없는 경우까지 count 해주면 출력값이랑 똑같이 나온다.

힌트를 나중에 봤는데 각 칸 별로 넴모가 있는 경우 없는 경우로 경우의 수를 계산하면
넴모가 4격자를 채우는 경우를 포함한 모든 경우를 좀 더 빨리 구할 수 있긴하다.
문제풀이 방식은 힌트를 기초하여 풀은 방식이다.

풀이 방법을 이해하는데 한참걸렸다.
우선 각 칸을 1로 차례차례 채우며 cnt를 증가시킨다.(넴모를 둔다는 의미)
만약 해당 칸에 넴모를 둬서 2x2 격자넴모가 완성되는 경우는 1을 두지 않고 0으로 남긴채로 cnt를 증가시킨다.
그리고 다시 나머지 칸을 채운다.
전체 격자 수만큼 cnt가 채워진 경우 answer를 1증가시킨다. (answer는 문제 조건에 맞게끔 칸이 채워진 경우를 의미)

# 2 x 3 의 격자의 경우 맨 처음에 이렇게 넴모가 채워진다.
# graph[1][1] 에 넴모(1)를 채우면 문제 조건에 만족하지 못하므로 이 경우는 건너뛰고 cnt만 증가시켜 진행한다.
1 1 1
1 0 1

# 그 다음 이런 식으로 graph[1][2]에 넴모를 제외한 식으로 확인하고
1 1 1
1 0 0

# 그 다음은 이렇게 graph[1][0] 에 넴모를 제외하고 그 뒤에 넴모를 채우는 방식으로
1 1 1
0 1 0

이렇게 해당 칸에 넴모를 넣는 경우와 빼는 경우를 문제에서 주어진 조건에 맞게끔 채우는 경우를 백트래킹 방식으로 반복한다.

(5) 참고

참고 풀이
이해잘되는 풀이

16987_계란으로 계란치기 (Python)

0. 출처

• 유형 : 백트래킹 (silver 1)
• 링크 : 16987번: 계란으로 계란치기

1. 기록

• 22/04/03 (일)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

'''
1. 아이디어
>>
>>

2. 시간복잡도
>>

3. 자료구조
>>
'''

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
3
8 5
1 100
3 5

- 예제 출력 1 -
3

- 예제 입력 2 -
3
1 100
8 5
3 5

- 예제 출력 2 -
2

- 예제 입력 3 -
1
123 45

- 예제 출력 3 -
0

- 예제 입력 4 -
8
222 117
176 92
287 6
284 81
221 96
263 96
188 40
225 1

- 예제 출력 4 -
4

- 예제 입력 5 -
6
65 281
272 145
233 175
229 12
99 88
142 159

- 예제 출력 5 -
6

(3) 코드

import sys

def check(eggs):
  count = 0
  for egg in eggs:
    if egg[0] <= 0:
      count += 1
  return count

def dfs(index, eggs):
  global answer

  if index == n:
    # 마지막 계란 까지 집은 경우
    answer = max(answer, check(eggs))
    return

  if eggs[index][0] <= 0:
    # 현재 계란의 내구도가 다 달았을 때 다음 계란으로 넘어간다.
    dfs(index + 1, eggs)

  else:
    # 현재 계란의 내구도가 남아있을 때 다른 계란들과 부딪친다. (현재 계란 제외, 내구도가 없는 계란 제외)
    is_all_broken = True
    for i in range(len(eggs)):
      if index != i and eggs[i][0] > 0:
        is_all_broken = False
        eggs[index][0] -= eggs[i][-1]
        eggs[i][0] -= eggs[index][-1]
        dfs(index + 1, eggs)
        eggs[index][0] += eggs[i][-1]
        eggs[i][0] += eggs[index][-1]

    # 모든 계란이 깨져있는 경우 dfs를 바로 빠져나와준다.
    if is_all_broken:
      dfs(n, eggs)

n = int(input())
eggs = []
answer = 0
for _ in range(n):
  eggs.append(list(map(int, input().split())))

dfs(0, eggs)
print(answer)

(4) 정리

예제 입력1 과 예제 입력2 의 결과가 왜 같은지 이해가 안되서 엄청 헤맸다.
처음에 모든 경우의 수로 다 쳐본다고 생각하고 시작했던게 이유였다.

• 무조건 가장 왼쪽(처음)의 깨지지 않은 계란을 먼저 들고 계란 치는 행위를 시작한다.(이때 어느걸 먼저 치던지 상관없다.)
• 경우1) 들었던 계란이 깨진 경우 깨지지 않은 다음 계란을 들고 계란 치는 행위를 반복한다.
• 경우2) 들었던 계란으로 다른 계란을 쳤는데 다른 계란이 깨지지 않은 경우 다음 계란을 들고 계란치는 행위를 반복한다.
• 모든 계란이 깨진 경우 종료한다.
• 마지막 계란을 들었을 경우도 종료한다.

(5) 참고

참고 풀이
이해가 쉬운 풀이

10971_외판원 순회2 (Python)

0. 출처

• 유형 : 백트래킹 (silver 2)
• 링크 : 10971번: 외판원 순회2

1. 기록

• 22/04/03 (일)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

'''
1. 아이디어
>>
>>

2. 시간복잡도
>>

3. 자료구조
>>
'''

(2) 예제 입력, 예제 출력

예제 입력 1
4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0

예제 출력 1
35

(3) 코드

n = int(input())
nums = [list(map(int, input().split())) for _ in range(n)]

depth = 0
answer = 99999999
visited = []

def recursive_dfs(city, depth, sum_cost, start):
    global answer

    # 순회를 마친 경우
    if depth == n:
        answer = min(answer, sum_cost)
        return

    for target in range(0, n):
        # 시작 지점으로 중간에 가지않으며 
        # target 이 city 가 되는 경우를 제외하고 
        # target 이 방문하지 않은 곳인 경우이고
        # city 에서 target 으로 갈때 0인 경우를 제외
        if target != start and target != city and target not in visited and nums[city][target] != 0:
            visited.append(target)
            sum_cost += nums[city][target]
            recursive_dfs(target, depth+1, sum_cost, start)
            sum_cost -= nums[city][target]
            visited.pop()

        # 마지막으로 시작지점으로 되돌아가기만 하면 되는 경우
        # city 에서 start 으로 갈때 0인 경우를 제외
        elif depth == n-1 and target == start and nums[city][start] != 0:
            visited.append(start)
            sum_cost += nums[city][start]
            recursive_dfs(city, depth + 1, sum_cost, start)
            sum_cost -= nums[city][start]
            visited.pop()

for city in range(n):
    sum_cost = 0
    target = 0
    start = city
    recursive_dfs(city, depth, sum_cost, start)

print(answer)

(4) 정리

코드를 어떻게 쉽게 작성해야 하나 고민중..
변수명만 적절하게 작성해도 어떻게 동작하는지 쉽게 그려져서 변수명에 신경을 잘 써야겠다.

(5) 참고

참고 풀이
질문 답변

1182_부분수열의 합 (Python)

0. 출처

• 유형 : 백트래킹, 브루트포스 (silver 2)
• 링크 : 1182번: 부분수열의 합

1. 기록

• 22/04/03 (일)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 부분 수열을 구한다.
>> 부분 수열의 합을 구하고 만족하는 부분수열을 카운트한다.

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
5 0
-7 -3 -2 5 8

- 예제 출력 1 -
1

(3) 코드

n, s = map(int, input().split())
nums = list(map(int, input().split()))

result = []

def iterative_dfs(index, path):
    # 매번 결과 추가
    result.append(path)

    for i in range(index, len(nums)):
        path = path+[nums[i]]
        iterative_dfs(i+1, path)

iterative_dfs(0, [])

cnt = 0

for answer in result:
    if answer != [] and sum(answer) == s:
        # print(answer)
        cnt += 1

print(cnt)

(4) 정리

(5) 참고

알고리즘 인터뷰 Q37. 부분집합 문제를 참고하면 좋습니다.

15666_N과 M(12)(Python)

0. 출처

• 유형 : 백트래킹 (silver 2)
• 링크 : 15666번: N과 M(12)

1. 기록

• 22/04/03 (일)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 주어진 수에 '중복된 숫자가 있을 때' 중복조합을 구하는 문제
>> set 이용 중복된 수를 제거하고 중복조합을 구한다.

2. 시간복잡도
>>

3. 자료구조
>>
'''

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
3 1
4 4 2

- 예제 출력 1 -
2
4

- 예제 입력 2 -
4 2
9 7 9 1

- 예제 출력 2 -
1 1
1 7
1 9
7 7
7 9
9 9

(3) 코드

n, m = map(int, input().split())
nums = list(map(int, input().split()))
nums = set(nums)
nums = list(nums)
nums = sorted(nums)

stack = []

def iterative_dfs(start):
    if len(stack) == m:
        print(*stack)
        return

    for i in range(start, len(nums)):
        stack.append(nums[i])
        iterative_dfs(i)
        stack.pop()

iterative_dfs(0)

(4) 정리

(5) 참고

15665_N과 M(11) (Python)

0. 출처

• 유형 : 백트래킹 (silver 2)
• 링크 : 15665번: N과 M(11)

1. 기록

• 22/04/03 (일)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 주어진 수 중에 중복된 숫자가 있을 때 중복순열을 구하는 문제
>> 주어진 수에서 중복된 숫자를 제거하고(set 이용) 그냥 중복순열을 구한다.

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
3 1
4 4 2

- 예제 출력 1 -
2
4

- 예제 입력 2 -
4 2
9 7 9 1

- 예제 출력 2 -
1 1
1 7
1 9
7 1
7 7
7 9
9 1
9 7
9 9

(3) 코드

n, m = map(int, input().split())
nums = list(map(int, input().split()))

set_nums = set(nums)
list_nums = list(set_nums)
nums = sorted(list_nums)

stack = []

def iterative_bfs():
    if len(stack) == m:
        print(*stack)
        return

    for i in range(0, len(nums)):
        stack.append(nums[i])
        iterative_bfs()
        stack.pop()

iterative_bfs()

(4) 정리

(5) 참고

15664_N과 M(10) (Python)

0. 출처

• 유형 : 백트래킹 (silver 2)
• 링크 : 15664번: N과 M(10)

1. 기록

• 22/04/03 (일)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 주어진 수 중에서 중복된 수가 있을 때 조합을 구하는 문제

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
3 1
4 4 2

- 예제 출력 1 -
2
4

- 예제 입력 2 -
4 2
9 7 9 1

- 예제 출력 2 -
1 7
1 9
7 9
9 9

(3) 코드

n, m = map(int, input().split())
nums = list(map(int, input().split()))
nums = sorted(nums)

visited = [False] * n
stack = []

def iterative_dfs(start):
    if len(stack) == m:
        print(*stack)
        return

    overlap_check = 0
    for i in range(start, n):
        if not visited[i] and overlap_check != nums[i]:
            visited[i] = True
            overlap_check = nums[i]
            stack.append(nums[i])
            iterative_dfs(i)
            stack.pop()
            visited[i] = False

iterative_dfs(0)

(4) 정리

(5) 참고

참고 풀이

15663_N과 M(9) (Python)

0. 출처

• 유형 : 백트래킹 (sliver 2)
• 링크 : 15663번: N과 M(9)

1. 기록

• 22/04/03 (일)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 주어진 수 중에서 '중복된 숫자가 있을 때' 순열을 만드는 문제

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
3 1
4 4 2

- 예제 출력 1 -
2
4

- 예제 입력 2 -
4 2
9 7 9 1

- 예제 출력 2 -
1 7
1 9
7 1
7 9
9 1
9 7
9 9

(3) 코드

n, m = map(int, input().split())
nums = list(map(int, input().split()))

nums.sort()
visited = [False] * n
stack = []

def solve(depth, n, m):
    if depth == m:
        print(' '.join(map(str, stack)))
        return
    overlap = 0
    for i in range(n):
        if not visited[i] and overlap != nums[i]:
            visited[i] = True
            stack.append(nums[i])
            overlap = nums[i]
            solve(depth+1, n, m)
            visited[i] = False
            stack.pop()

solve(0, n, m)

(4) 정리

기존 n과 m 문제를 푼 방식에서 조금 다양한 장치를 더 추가해야 된다.
visited 로 방문해야 될 숫자를 구별하고
overlap 변수로 중복된 수열을 출력하는 것을 방지한다.

# overlap 변수가 없는 경우

# 입력
4 2
9 7 9 1

# 출력
1 7
1 9
1 9
7 1
7 9
7 9
9 1
9 7
9 9
9 1
9 7
9 9

중복된 숫자 9를 구별하지 못한다.

(5) 참고

참고 풀이1
참고 풀이2

15657_N과 M(8) (Python)

0. 출처

• 유형 : 백트래킹 (silver 3)
• 링크 : 15657번: N과 M(8)

1. 기록

• 22/04/03 (일)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 주어진 수로 중복 조합만들기

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
3 1
4 5 2

- 예제 출력 1 -
2
4
5

- 예제 입력 2 -
4 2
9 8 7 1

- 예제 출력 2 -
1 1
1 7
1 8
1 9
7 7
7 8
7 9
8 8
8 9
9 9

(3) 코드

n, m = map(int, input().split())

nums = list(map(int, input().split()))
nums = sorted(nums)

stack = []

def iterative_bfs(start):
    if len(stack) == m:
        print(' '.join(map(str, stack)))
        return

    for i in range(start, len(nums)):
        stack.append(nums[i])
        iterative_bfs(i)
        stack.pop()

iterative_bfs(0)

(4) 정리

(5) 참고

17144_미세먼지 안녕! (Python)

0. 출처

• 유형 : 구현, 시뮬레이션 (gold 4)
• 링크 : 17144번: 미세먼지 안녕!

1. 기록

• 22/04/02 (토)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> r(행), c(열), t(시간) 입력받고
>> 미세먼지 graph 입력받고
>> 미세먼지 확산 A(r,c)/5
>> 위쪽 공기청정기 위치와 아래쪽 공기청정기 위치를 알아내야 한다.★★
>> 반시계 방향과 시계방향도 코드로 작성해줘야 한다.★★

2. 시간복잡도

3. 자료구조

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
7 8 1
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0

- 예제 출력 1 -
188

(3) 코드

import sys

r, c, t = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(r)]

up = -1
down = -1
# 공기 청정기 위치 찾기
for i in range(r):
    if arr[i][0] == -1:
        up = i
        down = i + 1
        break

# 미세먼지 확산
def spread():
    dx = [-1, 0, 0, 1]
    dy = [0, -1, 1, 0]

    tmp_arr = [[0] * c for _ in range(r)]
    for i in range(r):
        for j in range(c):
            if arr[i][j] != 0 and arr[i][j] != -1:
                tmp = 0
                for k in range(4):
                    nx = dx[k] + i
                    ny = dy[k] + j
                    if 0 <= nx < r and 0 <= ny < c and arr[nx][ny] != -1:
                        tmp_arr[nx][ny] += arr[i][j] // 5
                        tmp += arr[i][j] // 5
                arr[i][j] -= tmp

    for i in range(r):
        for j in range(c):
            arr[i][j] += tmp_arr[i][j]

# 위쪽 공기청정기 작동
def air_up():
    dx = [0, -1, 0, 1]
    dy = [1, 0, -1, 0]
    direct = 0
    temp = 0
    x, y = up, 1
    while True:
        nx = x + dx[direct]
        ny = y + dy[direct]
        if x == up and y == 0:
            break
        if nx < 0 or nx >= r or ny < 0 or ny >= c:
            direct += 1
            continue
        arr[x][y], temp = temp, arr[x][y]
        x = nx
        y = ny

# 아래쪽 공기청정기 작동
def air_down():
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    direct = 0
    temp = 0
    x, y = down, 1
    while True:
        nx = x + dx[direct]
        ny = y + dy[direct]
        if x == down and y == 0:
            break
        if nx < 0 or nx >= r or ny < 0 or ny >= c:
            direct += 1
            continue
        arr[x][y], temp = temp, arr[x][y]
        x = nx
        y = ny


for _ in range(t):
    spread()
    air_up()
    air_down()

answer = 0
for i in range(r):
    for j in range(c):
        if arr[i][j] > 0:
            answer += arr[i][j]

print(answer)

(4) 정리

arr[x][y], temp = temp, arr[x][y]

위와 같은 코드로

1. 현재 칸에 있는 값을 temp 변수에 집어넣고
2. 현재 칸 arr[x][y] 에 이전에 있던 칸의 값(temp)을 대입하는 식으로 값의 이동을 구현함을 배웠습니다.

(5) 참고

두 변수의 값 바꾸기 - swap
참고 풀이