[Python] 프로그래머스 등굣길, 백준 16918

1. 문제 - 프로그래머스 등굣길

https://school.programmers.co.kr/learn/courses/30/lessons/42898

 

해당 문제는 DP로 풀이할 수 있다. 이유는

- 완전 탐색으로 풀기에는 경우의 수가 너무 많고,

- 집에서 학교까지 도착하기까지의 시작과 종료 지점이 명확히 존재하며

- 최단경로의 개수는 이전 경로에서 가져와서 해를 구할 수 있기 때문이다.

 

❌ 틀린 풀이

def solution(m, n, puddles):
    dp = [[0] * m for _ in range(n)]
    
    for i in range(n):
        for j in range(m):
            if [j+1, i+1] in puddles:
                continue
            if i == 0 and j == 0:
                continue
            if i == 0 or j == 0:         # 이부분
                dp[i][j] = 1
                continue
            dp[i][j] = (dp[i-1][j] + dp[i][j-1])
                                
    return dp[n-1][m-1] % 1000000007

 

이 풀이에서 간과한게 있다.

처음에는 i가 0이거나 j가 0이면 오른쪽이나 아래쪽으로 갈 수 없으니 경로가 1개밖에 없으니까 모두 1이어야 하는거 아닌가? 했지만,

맨 위나 맨 왼쪽에 웅덩이가 있을 경우, 웅덩이 이후의 위치를 들릴 수 없으므로 이 경우에는 모두 0이어야한다.

위 풀이는 이 경우를 간과한 풀이이다.

 

✅ 풀이

def solution(m, n, puddles):
    dp = [[0] * m for _ in range(n)]
    
    for i in range(n):
        for j in range(m):
            if i == 0 and j == 0:
                dp[i][j] = 1
                continue
            if [j+1, i+1] in puddles:
                continue
            if i == 0:
                dp[i][j] = dp[i][j-1]
            elif j == 0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
                          
    return dp[n-1][m-1] % 1000000007

 

따라서 위와같이 수정할 수 있다.

1) 웅덩이는 모두 0으로 초기화하여 (여기서는 이미 배열을 0으로 초기화했으므로 continue 하기만 하면됨)

갈 수 있는 경로의 수를 0으로 지정하고,

2) 집을 1로 초기화 한 다음, i나 j가 0일 경우 (맨 왼쪽이거나 오른쪽일 경우, 즉 집에서 계속 오른쪽으로 가거나 아래쪽으로 이동하는 경우)이전 값을 그대로 가져오도록 한다. (i나 j가 0인 경우에는 한가지 루트밖에 없으므로 이전 값을 가져오는 것임)

3) 그 의외의 루트는, 왼쪽과 위쪽의 결과값을 더한 값으로 규칙을 찾아낼 수 있다.

2. 문제 - 백준 16918

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

 

✅ 풀이

r, c, n = map(int, input().split())   # rxc 직사각형, n초가 지난후의 격자판 상태 출력
board = []
bombs = []   # 폭탄 터뜨릴 좌표를 저장할 리스트 (3초 후에 터뜨리려면 기억하고있어야함)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def find_bomb():
  bombs.clear()

  for i in range(r):
    for j in range(c):
      if board[i][j] == "O":
        bombs.append((i, j))

for i in range(r):
  board.append(list(input()))

find_bomb()

def bang():
  for (x, y) in bombs:
    board[x][y] = "."
    
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if 0<=nx<r and 0<=ny<c:
        board[nx][ny] = "."    # 인접한 곳에 폭탄이 있어도 파괴되므로 따로 폭탄 여부 안따져도 됨

for i in range(2, n+1):    # 2, 4, 6, 8...은 폭탄을 설치하고 3, 5, 7... 은 폭탄 터뜨리고 좌표 저장함
  # 1. 폭탄 설치되어 있지 않은 모든 칸에 폭탄을 설치한다.
  if i % 2 == 0:
    board = [["O"] * c for _ in range(r)]
  else:  # 2. 3초 전에 설치된 폭탄이 모두 폭발한다.
    bang()
    find_bomb()   # 그 다음을 반복하기 위해 폭탄이 설치된 좌표를 저장함

for i in range(r):
  print("".join(board[i]))

 

먼저, 문제에서 폭탄 좌표를 찾고 상하좌우 인접한 4칸이 폭탄 여부와 관계없이 폭발시키는 과정이 반복되므로, 각각 find_bomb() 함수와 bang() 함수로 함수화했다.

 

1) 먼저 폭탄 좌표를 저장해두고 있다가 해당 폭탄과 상하좌우 인접한 칸을 폭파시켜야 하므로, board에 직사각형 격자판 정보를 입력받은 뒤 find_bomb 함수를 통해 폭탄 좌표들을 저장한다.

2) 그리고 "폭탄을 설치한다", "이전에 설치한 폭탄이 모두 폭발한다"를 반복하므로 이를 for문을 통해 반복한다.

for i in range(2, n+1):    # 2, 4, 6, 8...은 폭탄을 설치하고 3, 5, 7... 은 폭탄 터뜨리고 좌표 저장함
  # 1. 폭탄 설치되어 있지 않은 모든 칸에 폭탄을 설치한다.
  if i % 2 == 0:
    board = [["O"] * c for _ in range(r)]
  else:  # 2. 3초 전에 설치된 폭탄이 모두 폭발한다.
    bang()
    find_bomb()   # 그 다음을 반복하기 위해 폭탄이 설치된 좌표를 저장함

 

- 여기서 i가 2로 시작하는 이유는, 처음 1초는 아무것도 하지 않으므로 별다른 작업을 할 필요가 없기 때문에 2초부터 작업을 시작한다.

- 반복하는 형태를 보면, 2, 4, 6, 8...초는 모든 칸에 폭탄을 설치한다. 따라서 짝수초일 경우를 i%2 == 0으로 구분하여 board를 모든 칸에 폭탄이 설치된 보드로 초기화한다.

- 3, 5, 7, 9초...는 이전에 저장한 폭탄 좌표들과 해당 좌표들의 상하좌우 인접한 칸들이 폭파된다. 따라서 이 경우 bang() 함수를 통해 폭파시키고, 그 다음 작업을 반복하기 위해 현태 보드 상태에서의 폭탄 좌표들을 새롭게 저장한다. (find_bomb 함수)