수학과의 개발자 도전기

- 문제 : https://www.acmicpc.net/problem/1525

문제 이해 

- 3 x 3 행렬에서 0인 지점을 기준으로 bfs를 하는 문제다. 

- 0이 상하좌우 움직이면서 i행 j열의 값이 (3 * i + j) 값이 아닌 경우 0과 swap한다. 

- 0이 오른쪽 아래까지 갈 수 있는 최단 경로를 출력하는 문제다. 

- 처음에는 (행, 열) : 숫자 형식으로 딕셔너리를 만들었는데, 이렇게 하니 17%에서 계속 틀렸다. 이유로는 0이 상하좌우로 움직일 때마다 전체 행렬의 모습이 조금씩 달라지는데 그걸 공통 visit로 처리를 해서 각 케이스를 모두 담아내지 못해서 그런 것 같다. 

- 그래서 풀이를 찾아보니 전체 퍼즐 모양을 문자열로('123456780') 처리한 뒤, 그 문자열이 되기까지의 최단 경로를 딕셔너리에 저장하면 되었다. {퍼즐 모양(문자열) : 연산횟수} 형식이다.

- visit만 약간 형식이 다르고, 나머지는 일반 bfs로 풀면 된다.

풀이 로직

- 초기값을 입력받고 puzzle에 문자열로 저장한다.

- visit는 {'퍼즐순서' : 연산횟수}를 원소로 가지는 딕셔너리다.

- queue와 while문을 가지고 bfs를 진행하고, answer에 정답을 저장한다.

- 도착한 puzzle의 모양이 정답인 '123456780'인 경우 answer를 입력한다.

- 아직 정답에 도착하지 않았다면 문자열에서 0의 행, 열의 위치(x, y)를 찾은 다음, 이동 횟수(count)를 +1 한다.

-  상하좌우로 이동한 nx, ny의 값은 행렬의 값이므로, 이를 문자열에서의 인덱스 값으로 바꿔준다. nz = 3 * nx + y

- puzzle을 리스트로 바꾼 뒤, 문자열에서 nz의 값(0에서 상하좌우로 이동한 값)과 z의 값(0)을 바꾼다.

- 새로 바꾼 new_puzzle을 이전에 방문한 적이 없다면 딕셔너리 visit를 count로 갱신한 뒤 queue로 이동하면 된다.

정답 풀이 

from collections import deque

puzzle = ""
for i in range(3):
    puzzle += ''.join(list(input().split()))
    
visit = {puzzle : 0}
queue = deque()
queue.append(puzzle)
answer = -1
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

while queue:
    puzzle = queue.popleft()
    count = visit[puzzle]
    z = puzzle.index('0')
    
    if puzzle == '123456780':
        answer = count
        
    x, y = z // 3, z % 3   
    count += 1
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < 3 and 0 <= ny < 3:
            nz = nx * 3 + ny
            puzzle_list = list(puzzle)
            puzzle_list[z], puzzle_list[nz] = puzzle_list[nz], puzzle_list[z]
            new_puzzle = ''.join(puzzle_list)
            
            if new_puzzle not in visit.keys():
                visit[new_puzzle] = count
                queue.append(new_puzzle)
                
print(answer)

참고한 블로그 : [백준] 1525번 : 퍼즐

- 문제 : https://www.acmicpc.net/problem/14867

문제 이해

- 물통 a, b 가 있는데 몇 가지 방식에 의해 물을 채우고 비울 수 있다.

- 물통에 있는 물을 옮기는 규칙은 다음과 같다.

  1. 한 번에 가득 채우거나, 비울 수 있다.

  2. a -> b, b -> a로 물을 옮길 수 있다.

    a -> b인 상황을 예시로, b에 남은 공간에 따라 a가 줄 수 있는 물의 양은 달라진다.

    b의 남은 공간 > a 물의 양 일 때는 a에 있는 모든 물을 b에 옮길 수 있다.

    b의 남은 공간 < a 물의 양 일 때는 b의 남은 공간만큼만 a에서 옮길 수 있다. 

- 위의 움직임을 모두 bfs로 진행하면 된다. 1차 분기문으로 단순하게 나눠서 진행하면 될거라고 생각했지만, 케이스가 세세하게 생각이 안나서 좀 헤맸다. 

- 물통 비우기, 물통 가득 채우기, 물 옮기기 를 물통 a와 물통 b의 관점에서 생각하고 케이스를 짜면 쉽게 짤 수 있다.

풀이 로직

- 물통 a, b의 용량과 목표 용량을 입력 받고 중복 방문하지 않기 위해서 visit를 set으로 설정한다. 

  visit는 일차원 배열로 그 안에 원소가 있는 경우 방문한 것으로 생각한다. 

- while문으로 bfs를 진행하는데, 방문한 노드가 target이라면 answer를 갱신한 뒤 break 한다.

- 아직 target에 도착하지 못했다면 A 물통을 비웠을 때, 가득 채웠을 때, B 물통으로 물을 옮길 때를 분기문으로 작성하고, queue와 visit    처리를 해준다. 마찬가지로 B 물통을 비웠을 때, 가득 채웠을 때, A 물통으로 물을 옮길 때를 분기문으로 작성하고, queue와 visit 처리를    해준다. 

정답 풀이 

a, b, target_a, target_b = map(int, input().split())

queue = [[0, 0, 0]] # a에 있는 물의 양, b에 있는 물의 양, 연산횟수
visit = set()
visit.add((0, 0))

answer = -1
while queue:
    x, y, times = queue.pop(0)
    
    if x == target_a and y == target_b:
        answer = times
        break
    
    if (a, y) not in visit:
        visit.add((a, y))
        queue.append([a, y, times + 1])
    if (x, b) not in visit:
        visit.add((x, b))
        queue.append([x, b, times + 1])
    if (0, y) not in visit:
        queue.append([0, y, times + 1])
        visit.add((0, y))
    if (x, 0) not in visit:
        queue.append([x, 0, times + 1])
        visit.add((x, 0))
    
    if x + y >= b:
        if (x - b + y, b) not in visit:
            visit.add((x + y - b, b))
            queue.append([x + y - b, b, times + 1])
    else:
        if (0, x + y) not in visit:
            visit.add((0, x + y))
            queue.append([0, x + y, times + 1])

    if x + y >= a:
        if (a, x + y - a) not in visit:
            queue.append([a, x + y - a, times + 1])
            visit.add((a, x + y - a))
    else:
        if (x + y, 0) not in visit:
            queue.append([x + y, 0, times + 1])
            visit.add((x + y, 0))
            
print(answer)

참고한 블로그 : https://kingsol.tistory.com/10

- 문제 : https://www.acmicpc.net/problem/1039

문제 이해 

- 주어진 수의 i번째 자리수와 j번째 자리수를 k번 바꿔서 타겟 숫자가 될 수 있는지 출력하는 문제다.

- 문제가 그리디 같기도, 브루트포스? 같기도 해서 bfs로 어떻게 풀지 몰랐던 문제다. 

- 주의해야할 점은 두 가지가 있는데, 다음과 같다.

  1. 연산을 한 번 해서 이전과 같은 숫자가 나와도 다른 케이스로 쳐줘야 한다. 그래서 visit를 set으로 구현해서 원소들의 중복을 없애야 한다.

  2. 숫자를 바꿨을 때 가장 앞에 있는 수가 0이면 세지 않는다.  

- 그리고 i, j번째 수를 일일히 바꾸면 시간이 오래 걸리지 않을까 싶었는데 이중 for문으로 i, j를 바꾸면서 진행해야 했다. 

풀이 로직

- 입력값을 입력 받은 뒤 visit와 queue를 초기화 한다. 

  visit는 (진행하는 숫자, 연산횟수)를 원소로 가진 set

  queue는 [진행하는 숫자, 연산횟수]를 원소로 가진 배열

- while문으로 bfs를 진행하면서 연산횟수가 k와 같다면 정답 후보이다. 이때 answer = max(answer, 연산횟수)를 통해 가능한 최대값을 계속 업데이트한다.

- 연산횟수가 k가 아니라면 숫자를 배열로 변경한 뒤 이중 for문으로 i번째 수와 j번째 숫자를 바꾼다.

- 바꾼 숫자를 다시 ''.join()으로 하나의 숫자를 만들고 해당 숫자를 이전에 visit 하지 않았다면, visit 처리한 뒤 queue에 추가한다.

- 다른 숫자들도 숫자를 바꿔야 하므로 위에서 바꿨던 숫자를 다시 원상복구한다.

- while문에서 answer의 값이 0이 아니라면 정답이 있으므로 answer를 출력하고, 여전히 0이라면 -1을 출력한다.

정답 풀이 

n, k = map(int, input().split())
m = len(str(n))

visit = set()
visit.add((n, 0)) # 숫자, 연산횟수
queue = [[n, 0]]
answer = 0

while queue:
    number, times = queue.pop(0)
    
    if times == k:
        answer = max(answer, number) # 최대 숫자 업데이트
        continue
        
    number = list(str(number))
    for i in range(m - 1):
        for j in range(i + 1, m):
            if i == 0 and number[j] == '0':
                continue
            
            number[i], number[j] = number[j], number[i]
            temp = int(''.join(number))
            if (temp, times + 1) not in visit:
                queue.append([temp, times + 1])
                visit.add((temp, times + 1))
            # 배열 원상복구
            number[i], number[j] = number[j], number[i]
                
if answer == 0:
    print(-1)
else:
    print(answer)

참고한 블로그 : 백준-1039번-교환-파이썬

- 문제 : https://www.acmicpc.net/problem/9019

문제 이해

- 조건 D, S, L, R에 따라 숫자를 계산한 뒤 타겟 숫자까지 최소 몇 번의 연산으로 갈 수 있는지 출력하는 문제다.

- 이전에 풀었던 bfs 문제들처럼 조건으로 탐색한 뒤 queue를 이용하는 방식으로 구현했는데, 계속 시간초과가 발생했다.

- 찾아보니까 탐색할 때 분기문이 너무 많아지면 시간이 오래걸릴 수 있다고 한다. 그래서 미리 숫자들을 계산한 뒤 각 케이스를 for문 탐색으로 진행하는 것이 아닌 단일 분기문으로 처리하면 통과한다.

- python으로는 시간초과가 발생해서 pypy3로 진행했다.

풀이 로직

- 시작 숫자(a)와 타겟 숫자(b)를 입력 받는다.

- bfs 진행 할 queue와 중복 숫자 방문을 방지하기 위한 visit 배열을 초기화한다. 

queue는 [숫자, 그 숫자까지의 연산 문자들] 원소로 이뤄져있고, visit[숫자] = 1은 숫자를 이전에 방문했다는 표시이다.

- while문으로 bfs를 진행하면서 타겟을 찾은 경우 문자열을 출력한 뒤 while문을 break 한다

- 조건 D, S, L, R에 맞는 숫자들 dd, ds, dl, dr을 계산한 뒤 각 케이스별로 방문하지 않은 숫자이면 방문처리 후 탐색을 마저 진행하면 된다.

정답 풀이

분기문 줄일 수 있게 미리 숫자 계산하기

dd, ds, dl, dr은 모두 한번의 연산으로 진행하는 것이 빠름 + dl, dr은 문자열이 아니라 수학으로 풀자

from collections import deque

for _ in range(int(input())):
    a, b = map(int, input().split())
    
    queue = deque()
    queue.append([a, ''])
    visit = [0] * 10000
    visit[a] = 1
    while queue:
        x, words = queue.popleft()
        
        if x == b :
            print(words)
            break
        
        dd = 2 * x % 10000
        ds = (x - 1) % 10000
        dl = x // 1000 + (x % 1000) * 10
        dr = x // 10 + (x % 10) * 1000
        if not visit[dd]:
            visit[dd] = 1
            queue.append([dd, words + 'D'])
            
        if not visit[ds]:
            visit[ds] = 1
            queue.append([ds, words + 'S'])
        
        if not visit[dl]:
            visit[dl] = 1
            queue.append([dl, words + 'L'])
            
        if not visit[dr]:
            visit[dr] = 1
            queue.append([dr, words + 'R'])