수학과의 개발자 도전기

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

Gold Lv4 문제이고, 풀이 없이 풀었다. 생각보다 조건을 세세하게 나눴어야 해서 여러번 시도를 했던 문제이다.

문제 이해 

- A, B 버튼을 t번 이하로 눌러서 n을 g로 최소 시간 안에 만들 수 있는지 확인하는 문제다. 만약 못 만든다면 ANG를 출력한다.

- A 버튼과 B 버튼의 동작방식은 다음과 같다.

   A 버튼 : (이전 수) + 1

   B 버튼 : (이전 수) * 2 -> 가장 큰 자릿수 - 1

- 실패하는 케이스도 잘 생각해야하는데, 만약 A버튼을 누르거나, B 버튼에서 곱하기 2를 했을 때 10 ** 6 이상이 되면 실패한 케이스이다. 

- 풀면서 헤맸던 부분은 다음과 같다.

  1. bfs인데 방문한 노드를 visit 처리하지 않았던 것

  2. 다음 노드가 범위 내(1 이상 99999 이하)여야 한다는 것이다. 

  3. A버튼과 B버튼이 이동방식이 달라서 visit 처리를 해줘야하는 노드들도 다르다.

풀이 로직 

- n, t, g를 입력값으로 받고, 방문하는 숫자들을 처리하기 위해 visit를 초기화 한다. (최대 숫자가 99999이므로 길이는 넉넉하게 10 ^ 5 + 1)

- queue에 n을 추가한 다음 while문으로 bfs를 진행한다. 

- 방문한 노드가 g와 같고, visit[number] - 1 값이 t 이하라면 정답이므로 visit[number] - 1을 출력한 뒤 while 문을 break한다. (visit 시작 값이 1로 시작해서 정답과 1 차이가 나기 때문에 -1을 해줬다)

- 방문한 노드가 g가 아니라면 다음 노드로 이동하는데, 다음 노드가 범위 내 [1, 99999]에 있는지 확인한다. 만약 다음 노드가 범위 내에 없다면 문제에서 바로 실패라고 했으므로 for문을 break한다. 

- 다음 노드가 범위 내에 있을 때, A 버튼인지 B 버튼인지에 따라 다음 노드 값이 달라진다. 

A 버튼인 경우는 number + 1를 방문하지 않은 경우 이동할 수 있고, 이에 따라 visit 처리하고, queue에 추가하면 된다.

if each == number + 1:
    if not visit[each]:
        queue.append(each)
        visit[each] = visit[number] + 1

B 버튼인 경우 2 * number가 다음 노드가 아니라 2배 한 뒤 최대 자리수 값을 -1 해야한다. 그래야 최종값인 temp가 된다. 

이 temp를 방문하지 않은 경우 방문 처리 후, queue에 추가하면 된다.

elif each == number * 2:
    count = len(str(each))
    temp = each - 10 ** (count - 1)
    if not visit[temp]:
        queue.append(temp)
        visit[temp] = visit[number] + 1

- while문을 다 돌았는데도 정답을 출력하지 못했으면 실패한 것이므로 ANG를 출력한다. 

정답 풀이 

항상 visit 배열로 방문 여부 확인해야 시간초과 안 뜨고, 

다음 노드가 범위 내에 있는지 확인 해야함 

이 문제에서는 다음 노드가 어디인지에 따라 노드 값이 변형될 수 있으므로 그 부분 주의하기

from collections import deque

n, t, g = map(int, input().split())

queue = deque() # 숫자, 횟수 
queue.append(n)
flag = False
visit = [0] * (10 ** 5 + 1)
visit[n] = 1
while queue:
    number = queue.popleft()
    
    if number == g:
        if visit[number] - 1 <= t:
            flag = True
            print(visit[number] - 1)
            break             
        
    for each in [number + 1, number * 2]:
        if 1 <= each <= 99999 :
            if each == number + 1:
                if not visit[each]:
                    queue.append(each)
                    visit[each] = visit[number] + 1
            elif each == number * 2:
                count = len(str(each))
                temp = each - 10 ** (count - 1)
                if not visit[temp]:
                    queue.append(temp)
                    visit[temp] = visit[number] + 1
        else:
            break
                
if flag == False:
    print('ANG')

삽질기록,,,

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

Gold Lv4 문제이고, 풀이 없이 풀었다! 사실 이전에 풀었던 불 문제와 풀이가 비슷했다. 

문제 이해 

- 고슴도치(S)가 물이 번지는 상황에서 물에 잠기지 않고 무사히 비버 소굴(D)로 최소 시간에 갈 수 있는지 확인하는 문제다.

- 고슴도치와 물 둘 다 bfs로 진행해야하기 때문에 둘다 모두 queue에 넣어서 진행해야한다.

- 고슴도치는 matrix에서 '.', 'D'인 지점을 지날 수 있고, 물은 '.' 인 지점만 갈 수 있다.

하지만 시간을 아끼기 위해서는 고슴도치와 물 모두 각 지점이 ' . '이거나 'D'인 지점을 탐색할 수 있게 했다. (물은 'D' 지점을 못 가기 때문에 추가 조건을 달아준다, 이렇게 한 이유는 이전에 고슴도치, 물 각각 따로 분기문으로 나눠서 진행했는데 시간초과가 발생했기 때문이다)

- 고슴도치가 가는 길은 양의 정수로 진행하고, 물이 지나가는 곳은 -1 처리를 해서 고슴도치가 못가게 한다.

풀이 로직

- 입력값(n, m, matrix)을 입력받으면서 고슴도치의 위치, 비버 소굴의 위치, 물의 위치를 저장한다. 

- queue에 이동하는 위치를 추가할 건데, 이때 어떤 객체가 움직이는지 확인하기 위해 [행, 열, 'kaktus'(고슴도치)'], [행, 열, 'water'(물)]의 형태로 데이터를 추가한다. 

- 물의 위치는 queue에 입력하고, 고슴도치와 비버 소굴의 위치는 (a, b), (c, d)에 입력한다.

     - 고슴도치와 물의 초기 위치를 visit에 기록한다. (고슴도치는 visit[i][j] = 1, 물은 visit[i][j] = -1 -> 이렇게 초기 설정을 하지 않으면            틀리거나 시간초과가 발생한다)

     - 물(*)의 위치를 queue에 먼저 넣는 이유는 고슴도치는 물이 번질 곳으로는 이동하면 안되기 때문이다.

- while문을 진행하면서 도착한 위치가 비버 소굴이고, 객체가 고슴도치라면 정답이므로 답을 저장한 다음, flag = True 설정 후 break한다.

    - 답이 visit[x][y] - 1인 이유는 처음 시작을 1로 시작했기 때문에 정답보다 1 크기 때문이다.

- 아직 도착하지 않았다면 범위 내에서 상하좌우를 탐색한다. 이때 각 노드들은 다음 노드를 방문하지 않았고, matrix의 값이 '.' 또는 'D'인 지점만 방문 가능하다. 

- 고슴도치인 경우 visit[다음노드]로 시간 1을 들여 이동한다. 물이라면 matrix == '.' 인 지점만 이동 가능하고, visit[다음노드]를 -1 처리하고 이동한다. 

- 만약 반복문을 다 돌아도 flag == False 라면 실패한 것이므로 'KAKTUS'를 출력한다. 아니라면 그대로 정답을 출력하면 된다.

정답풀이 

n, m = map(int, input().split())
matrix = []
a, b = 0, 0 # 고슴도치 위치 
c, d = 0, 0 # 비버 소굴 위치
queue = []
visit = [[0] * m for _ in range(n)]
for i in range(n):
    matrix.append(list(input()))
    for j in range(m):
        if matrix[i][j] == 'D':
            c, d = i, j
        if matrix[i][j] == 'S':
            a, b = i, j
            visit[i][j] = 1
        if matrix[i][j] == '*':
            queue.append([i, j, 'water'])
            visit[i][j] = -1
            
queue.append([a, b, 'kaktus'])
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
answer = 0
flag = False
while queue:
    x, y, kind = queue.pop(0)
    
    if x == c and y == d:
        if kind == 'kaktus':
            flag = True
            answer = visit[x][y] - 1
            break
    
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if not visit[nx][ny] and (matrix[nx][ny] == '.' or matrix[nx][ny] == 'D'):
                if kind == 'kaktus':
                    visit[nx][ny] = visit[x][y] + 1
                    queue.append([nx, ny, 'kaktus'])
                if kind == 'water':
                    if matrix[nx][ny] == '.':
                        visit[nx][ny] = -1
                        queue.append([nx, ny, 'water'])
                    
if flag == False :
    print('KAKTUS')
else:
    print(answer)

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

문제 이해 

- 건물에서 불이 번져가는데, 상범이는 불에 닿지 않고 무사히 불을 탈출할 수 있는지 확인하는 문제다

- 상범이뿐만 아니라 불도 bfs로 진행되어야 한다. 그래서 초기 행렬 값을 입력 받을 때 불과 상범이의 위치, 타입을 queue에 입력 받아야 한다. (예 : [i, j, 'person'], [i, j, 'fire'])

- 각 초기 위치를 방문 처리해줘야 시간초과가 발생하지 않는다.

- 불이 번질 예정인 곳은 상범이가 못 가므로, 초기에 불의 위치를 모두 입력받은 다음 마지막에 상범이의 위치를 추가한다. 

- bfs를 진행하면서 상범이가 이동하는 것과 불이 이동하는 것을 구분해야한다. 상범이의 이동은 양의 정수로 +1 씩 하며 이동하고, 불이 이동하는 곳은 -1 처리한다. 

- 따로 탈출구가 명시되어 있지 않은데, 탈출구는 0행, n - 1행, 0열, m - 1열 중에 '.'인 어느 지점이든 탈출구가 될 수 있다. 

풀이 로직

- 여러 케이스가 있으므로 각 케이스마다 bfs를 진행한다. 

- 입력값(m, n, matrix)를 입력 받고 visit를 초기화 한다.

- 정답을 찾은 경우와 못 찾은 경우를 분리하기 위해 flag를 사용한다.

- 행렬값을 입력 받으면서 불의 위치와 타입('fire')을 queue에 입력하고 visit 값을 -1로 방문처리 한다. 상범의 위치는 person에 저장한 뒤 visit 값을 1로 방문처리 한다. 

- 불의 초기 위치를 모두 queue에 저장한 뒤 마지막으로 person의 위치와 타입('person')을 queue에 추가한다.

- while문으로 bfs를 수행하는데, 도착한 지점이 탈출구(탈출구는 0행, n - 1행, 0열, m - 1열 중에 '.'인 어느 지점)인 경우 visit[x][y]을 출력한 뒤 while문을 break한다. 

- 답을 찾지 못했다면 상하좌우로 다음 노드를 탐색하는데, 다음 조건을 만족하는 노드여야한다.

1. 방문하지 않았음

2. matrix의 값이 '.' 또는 '@'여야한다. (상범이는 '.'만 이동가능, 불은 '.', '@' 모두 이동가능한데 하나의 if문으로 처리하지 않으면 시간초과가 발생한다)

if not visit[nx][ny] and (matrix[nx][ny] == '@' or matrix[nx][ny] == '.'):

- 타입에 따라 visit 처리와 queue에 값을 삽입한다. 

- while문을 돌면서도 답을 찾지 못했다면 'IMPOSSIBLE'을 출력한다.

정답 풀이 

from collections import deque
import sys
input = sys.stdin.readline

for _ in range(int(input())):
    m, n = map(int, input().split())
    matrix = []
    queue = deque()
    person = ()
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    visit = [[0] * m for _ in range(n)]
    
    for i in range(n):
        matrix.append(list(input()))
        for j in range(m):
            if matrix[i][j] == '*':
                queue.append([i, j, 'fire'])
                visit[i][j] = -1
            if matrix[i][j] == '@':
                person = (i, j, 'person')
                visit[i][j] = 1
    queue.append(person)
    
    flag = False
    while queue:
        x, y, kind = queue.popleft()
        if x == 0 or x == n - 1 or y == 0 or y == m - 1:
            if kind == 'person':
                flag = True
                print(visit[x][y])
                break
            
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                # kind가 person, fire인 경우 모두에 아래 조건을 적용해야 메모리 초과가 발생하지 않는다.
                if not visit[nx][ny] and (matrix[nx][ny] == '@' or matrix[nx][ny] == '.'):   
                    if kind == 'person':
                        visit[nx][ny] = visit[x][y] + 1
                        queue.append([nx, ny, 'person'])
                    if kind == 'fire':
                        visit[nx][ny] = -1
                        queue.append([nx, ny, 'fire'])
    
    if flag == False:
        print('IMPOSSIBLE')

참고한 블로그 : 블로그

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

문제 이해 

- 0인 지점을 중심으로 bfs로 진행하다가 1을 만났을 때 한 번만 벽을 부숴서 진행할 수 있는 문제다.

- 벽을 1번만 뚫었는지 확인하기 위해 원소가 [0, 0]인 n x m 행렬을 이용한다.

0열에 값이 있으면 이전에 벽을 한번도 안 뚫은 경로이고, 1열에 값이 있으면 이전에 한 번 벽을 뚫은 경우이다. 

- 이전에 벽을 뚫었는지 여부를 일일히 visit[i][j][1] 값으로 확인해야돼서 케이스 나누는 게 복잡하다고 생각했는데 그게 아니라 

isCrash를 가지고 visit[i][j][isCrash]의 값으로만 진행하면 훨씬 간단해졌다.

풀이 로직

- n, m, matrix를 입력값으로 받는다.

- [0, 0]가 원소인 n x m 행렬 visit와 [i, j, isCrash] 원소를 추가하는 queue를 초기화한다.

- queue에서 x, y, isCrash를 얻은 다음, x == n - 1 and y == m - 1인 경우에 visit[x][y][isCrash]를 출력하고 while문을 탈출한다.

- x, y 위치에서 범위내의 상하좌우 값 중에 2가지 경우를 고려한 뒤 visit 값을 변경시키고, queue에 추가하면 된다.

1. 다음 노드의 값이 0이고, 아직 방문하지 않은 경우 : 이전에 벽을 뚫었건, 뚫지 않았건 상관없으므로 일반적인 bfs 적용하면 된다.

2. 다음 노드의 값이 1이고, isCrash == 0 인 경우 : 벽을 만났고, 이전에 벽을 부순적이 없다면 해당 벽을 부수고 이동할 수 있다. 

- 만약 while문에서 답을 출력하지 못했다면 답이 없는 경우이므로 -1을 출력한다. (상황은 flag 값으로 구분한다)

정답 풀이

from collections import deque

n, m = map(int, input().split())
matrix = []
for _ in range(n):
    matrix.append(list(map(int, input())))
    
visit = [[[0, 0] for _ in range(m)] for _ in range(n)]
visit[0][0][0] = 1
queue = deque()
queue.append([0, 0, 0])
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
flag = False
while queue:
    x, y, isCrash = queue.popleft()
    
    if x == n - 1 and y == m - 1:
        flag = True
        print(visit[x][y][isCrash])
        break
    
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if matrix[nx][ny] == 0 and not visit[nx][ny][isCrash]:
                visit[nx][ny][isCrash] = visit[x][y][isCrash] + 1
                queue.append([nx, ny, isCrash])
            if matrix[nx][ny] == 1 and isCrash == 0:
                visit[nx][ny][isCrash + 1] = visit[x][y][isCrash] + 1
                queue.append([nx, ny, isCrash + 1])
     

if flag == False:
    print(-1)