[Python] 프로그래머스 숫자게임, 백준 청소년 상어

1. 문제 - 프로그래머스 숫자게임

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

 

💡 문제 접근 방식

본래라면 A팀의 각 원소마다 더 큰 원소들을 찾아 그 합계를 구하려면, 이중 반복문이 되지만 A와 B는 1이상 100,000 이하이기 때문에 시간초과가 발생한다.

따라서 기존 시간초과 발생 코드를 O(N)을 통해 효율적으로 찾을 수 있게 해주는 투포인터 알고리즘을 사용한다.

 

✅ 풀이

def solution(A, B):
    A.sort()     # 차례대로 움직이며 B가 A보다 더 큰 원소를 찾아야하므로, 둘다 오름차순으로 정렬한다.
    B.sort()
    answer = 0
    
    idx_A, idx_B = 0, 0
    while idx_A < len(A) and idx_B < len(B):
        if A[idx_A] < B[idx_B]:
            idx_A += 1   # B가 더 큰 인덱스를 찾았으므로 그 다음 수를 비교하기 위해 idx_A, idx_B 둘다 + 1
            idx_B += 1
            answer += 1
        else:    # B가 더 큰 인덱스를 찾아다니기 위해 idx_B만 + 1
            idx_B += 1
    
    return answer

 

2. 문제 - 백준 청소년 상어 (삼성 SW 역량테스트 기출)

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

 

💡 문제 접근 방식

 

기본적으로 시뮬레이션/구현 문제이다. 그런데 "상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구해보자." 에서 어떻게 최대값을 구할 수 있을지에서 아이디어가 막혔다.

다른 사람의 풀이를 찾아보니 DFS를 사용하여 풀이할 수 있고, 문제에서 어떻게 DFS 키워드를 잡고 접근할 수 있을지 고민해보았다.

 

1) "청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다."

- 시작점이 정해져있음. 그러나 여기까지는 단순 시뮬레이션 문제로 보일 수 있다

 

2) “상어는 현재 방향으로 1칸 이상 이동 가능하며, 물고기가 있는 칸만 이동 가능하다.”

- 현재 있는 칸 마다 선택지가 여러개 선택할 수 있다 --> 가지치기 (상태분기) --> 그래프탐색 유추

 

3) 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다.

이 과정이 반복될때, 상어가 먹을 수 있는 물고기 번호 합의 최대값을 구해보자.

- 상어가 더이상 이동할 수 없는 칸까지 이동함 = 깊이 우선 탐색

- 이 때, 최대값을 보장할 수 없으므로 이전 상태를 복구하여 다시 탐색해야함 = 백트래킹

 

✅ 나의 풀이

import copy

dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]  # 1부터 8까지 차례대로 방향 offset 배열
answer = 0

fishes = []            # 물고기 번호 적힌 보드
f_directions = []      # 물고기 번호마다 움직이는 방향 적힌 보드

for _ in range(4):     # 입력받기
  temp = list(map(int, input().split()))
  fish = []
  dir = []
  for j in range(8):
    if j%2 == 0:
      fish.append(temp[j])
      if len(fish) == 4:
        fishes.append(fish)
        fish = []
    else:
      dir.append(temp[j]-1)    
      if len(dir) == 4:
        f_directions.append(dir)
        dir = []

def find_coord(board, num):    # 물고기 좌표 찾기
  for i in range(4):
    for j in range(4):
      if board[i][j] == num:
        return i, j

  return -1, -1   # 못찾은 경우

def moving_fishes(board, directions, shark_x, shark_y):
  for i in range(1, 17):  # 번호가 작은 물고기부터 이동한다.
    x, y = find_coord(board, i)   # 물고기 좌표 찾기
    
    if x == -1 and y == -1:    # 이미 먹힌 물고기이므로, 다음 물고기의 이동 작업을 시작한다.
      continue
      
    dir = directions[x][y]
      
    for j in range(8): 
      # 이동할 수 있는 칸을 찾을 때까지 45도 반시계 회전시킨다.
      nd = (dir + j) % 8
      nx = x + dx[nd]
      ny = y + dy[nd]

      # 이동할 수 없는 칸: 경계를 벗어나거나, 상어가 있거나
      if not (0<=nx<4 and 0<=ny<4): 
        continue

      if nx == shark_x and ny == shark_y:
        continue

      # 이동할 수 있는 칸이 있다면, 물고기와 방향 포함해서 같이 위치 바뀜
      board[nx][ny], board[x][y] = board[x][y], board[nx][ny]
      directions[x][y] = nd  # 이동할 수 있는 방향으로 갱신한 다음,
      directions[x][y], directions[nx][ny] = directions[nx][ny], directions[x][y]   # 서로 바꿔주기
      break    # 이동할 수 있는 칸을 찾았으므로 break
      
def positions_shark_can_go(board, shark_x, shark_y, dir):
  positions = []
  
  for _ in range(3):   # 상어는 방향에 있는 칸으로 이동할 수 있고, 한번에 여러개의 칸을 이동할 수 있다.
    shark_x += dx[dir]
    shark_y += dy[dir]

    if 0<=shark_x<4 and 0<=shark_y<4 and board[shark_x][shark_y] != 0:        # 물고기가 없는 칸으로는 이동할 수 없다.
      positions.append((shark_x, shark_y))

  return positions

def dfs(x, y, board, directions, total):
  global answer

  # 상태마다 board의 상태가 바뀌므로 복사 필요함
  copied = copy.deepcopy(board)
  copied_directions = copy.deepcopy(directions)
  
  total += copied[x][y]   # 물고기를 먹음
  copied[x][y] = 0        # 먹는 상태로 처리

  moving_fishes(copied, copied_directions, x, y)   # 물고기 움직임

  positions = positions_shark_can_go(copied, x, y, copied_directions[x][y])

  if not positions:           # 더이상 이동할 수 없다면 answer 갱신하고 되돌아가기
    answer = max(answer, total)
    return

  for nx, ny in positions:   # 이동할 수 있는 모든 칸에 대해 탐색 진행
    dfs(nx, ny, copied, copied_directions, total)

# 0, 0에서부터 시작함
dfs(0, 0, fishes, f_directions, 0)

print(answer)

 

여기서 물고기의 방향과 함께 입력받고 처리하는 부분을 개선할 수 있다면 다음과 같이 개선할 수 있다.

board를 3차원 배열로 만들어 처리하여 개선하면 코드가 다음과 같다.

fishes = []          # 입력받기
for _ in range(4):
  temp = list(map(int, input().split()))
  row = []
  for j in range(0, 8, 2):
    a, b = temp[j : j + 2]
    row.append([a, b - 1])   # 물고기 번호, 방향
  fishes.append(row)

def find_coord(board, num):    # 물고기 좌표 찾기
  for i in range(4):
    for j in range(4):
      if board[i][j][0] == num:
        return i, j

  return -1, -1   # 못찾은 경우

def moving_fishes(board, shark_x, shark_y):
  for i in range(1, 17):  # 번호가 작은 물고기부터 이동한다.
    x, y = find_coord(board, i)   # 물고기 좌표 찾기
    
    if x == -1 and y == -1:    # 이미 먹힌 물고기이므로, 다음 물고기의 이동 작업을 시작한다.
      continue
      
    dir = board[x][y][1]    # 기존 방향
      
    for j in range(8): 
      # 이동할 수 있는 칸을 찾을 때까지 45도 반시계 회전시킨다. 처음 방향도 가능할 수 있으므로 j는 0부터 시작한다.
      nd = (dir + j) % 8
      nx = x + dx[nd]
      ny = y + dy[nd]

      # 이동할 수 없는 칸: 경계를 벗어나거나, 상어가 있거나
      if not (0<=nx<4 and 0<=ny<4): 
        continue

      if nx == shark_x and ny == shark_y:
        continue

      # 이동할 수 있는 칸이 있다면, 물고기와 방향 포함해서 같이 위치 바뀜
      board[x][y][1] = nd  # 주의!!: 이동할 수 있는 방향으로 갱신한 다음,
      board[nx][ny], board[x][y] = board[x][y], board[nx][ny]
      break    # 이동할 수 있는 칸을 찾았으므로 break

def dfs(x, y, board, total):
  global answer

  # 상태마다 board의 상태가 바뀌므로 복사 필요함
  copied = copy.deepcopy(board)
  
  total += copied[x][y][0]   # 물고기를 먹음
  copied[x][y][0] = 0        # 먹는 상태로 처리

  moving_fishes(copied, x, y)   # 물고기 움직임

  positions = positions_shark_can_go(copied, x, y, copied[x][y][1])


... 이하 동일