[CodeUp] 6098 성실한 개미 (파이썬)

문제 링크

문제 설명

미로 상자의 구조와 먹이의 위치가 입력될 때 개미가 이동한 경로를 9로 표시해 출력하는 코드 작성

풀이 코드

box = [list(map(int, input().split())) for _ in range(10)]
start = [1, 1]
dy = [0, 1]
dx = [1, 0]

def find(location):
  y, x = location
  box[y][x] = 9
  for i in range(len(dy)):
    point = box[y+dy[i]][x+dx[i]]
    if point == 0:
      y += dy[i]
      x += dx[i]
      find([y, x])
      break
    if point == 1:
      continue
    if point == 2:
      y += dy[i]
      x += dx[i]
      box[y][x] = 9
      break

    
find(start)

for item in box:
  print(*item)

코드 설명

0. 개미가 방향을 찾고, 먹이를 찾아 값을 변환한 뒤 다시 이 과정을 반복한다는 점에 착안하여 재귀함수를 호출하는 방법을 적용하기로 함
   개미는 벽(1)을 만나면 다른 방향을 탐색하고, 음식(2)를 만나면 9로 변환한 뒤 멈춘다는 부분을 종료조건으로 설정함
1. 초기 시작점 좌표 [1, 1]및 탐색방향(dy, dx)을 설정
2. 함수 선언 시 자기 자리 값을 9로 변환하고 다음 나아갈 방향 탐색(point)
3. point가 0일 때 현재 위치를 변환하고 다시 find() 호출
4. point가 1일 때 다른 방향을 탐색하고, point가 2일 때 해당 위치 값을 9로 변경 및 재귀함수 탈출
5. 값이 모두 변환된 box 배열 언패킹 후 출력

cf) DFS 알고리즘에서 격자 내 자기 자신의 위치를 이동하기 위한 dy, dx값은 아래 사진과 같음 (출처 : Tanvir Sojal / Youtube)