[Code Tree][Python] BFS / K번 최댓값으로 이동하기

Overview

• 체감 난이도: ★★★☆☆  * 어렵다...
• 문제 유형: BFS
• 풀이 상태: 답안참고 / 스스로 해결
• 추후: 다시 풀어보기 / 간단 복습 / 완벽 이해 

---

[문제]

K번 최댓값으로 이동하기

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

[문제 이해]

• 주어진 격자에서 특정 위치에서 시작하여 이동할 수 이는 칸 중 최댓값이 적힌 칸으로 이동하는 것을 반복한다. 
• 이동할 수 있는 칸의 조건은 현재 위치의 칸 숫자보다 작은 숫자가 적힌 칸이어야 한다. 
  • 숫자가 동일한 칸이 여러 개 있을 경우, 행 번호가 작은 칸 순, 행 번호도 같다면 열 번호가 작은 칸 순으로 선택한다. 
  • 현재 칸에서 상하좌우로 이동할 수 있는 칸만 이동할 수 있다. 
    • 시작 위치의 상하좌우가 시작 위치 칸의 숫자보다 큰 숫자들이면 이동이 불가능하다. 
• 이 과정을 최대 K번 반복한다. 단, 더 이상 이동할 수 있는 칸이 없으면 멈춘다. 
• 최종적으로 K번 이동하거나, 이동이 불가능해서 멈췄을 때 도달한 위치를 출력한다. 

 

[풀이 아이디어]

1. 현재 시작 위치(입력으로 받음)를 큐에 넣어 bfs를 호출하여, 현재 위치에서 이동할 수 있는 칸들을 visited 배열에 기록한다. 
   1. 이동 조건(1. 현재 칸 숫자보다 작을 것, 2. 상하좌우로 이동 가능한 위치일 것 )
   2. 좌표가 바뀔 때마다 bfs를 다시 호출해야 하므로 visited 배열을 초기화 해줘야 한다. 
2. k번 횟수만큼 for문을 구현 → 기록된 visited 배열을 돌면서,
   1. 칸의 숫자가 큰 순, 행의 번호가 작은 순, 열의 번호가 작은 순으로 비교하며
   2. 이동할 칸을 갱신해준다. 
   3. 이동할 칸이 없다면 반복문 종료

 

[트러블슈팅 & 배운 점]

💥 문제 발생

→ NOT_EXISTS = [-1, -1] 선언 해주지 않고, best_pos == [-1, -1] 바로 직접적인 배열을 사용해 출력값이 다름

 

🤔 why?

→ NOT_EXISTS를 [-1, -1]로 변수로 지정한 후 사용한 경우와, [-1, -1]를 직접 사용한 경우 결과가 다르게 나오는 이유는 Python 리스트 비교 방식과 메모리 참조 방식과 관련 있다. 

 

1. NOT_EXISTS 변수를 사용할 때

- NOT_EXISTS라는 변수를 선언하고 사용하면, NOT_EXISTS는 하나의 리스트 객체를 가리킨다.

- 만약 코드에서 best_pos = NOT_EXISTS라고 한다면, best_pos도 NOT_EXISTS와 같은 리스트 객체를 참조하게 된다.

- 따라서 나중에 if best_pos == NOT_EXISTS:와 같은 비교문을 사용할 때 best_pos와 NOT_EXISTS는 같은 객체이므로 이 비교는 True로 평가된다.

 

2. [-1, -1]를 직접 사용할 때

- [-1, -1]을 코드에서 직접 반복해서 사용하면, Python은 각 [-1, -1] 표현을 새로운 리스트 객체로 인식한다.

- 예를 들어, best_pos = [-1, -1]라고 했을 때 best_pos는 새로 생성된 리스트 [-1, -1]를 참조하고 있다.

- 이렇게 할 경우, if best_pos == [-1, -1]:는 두 리스트가 값은 같지만 서로 다른 객체이기 때문에, best_pos와 [-1, -1]을 같은 객체로 인식하지 않을 수 있다.

- 다만, == 연산은 두 객체의 값만을 비교하기 때문에 값이 같다면 True로 평가된다. 하지만, 객체의 참조나 특정 조건에 따라 예기치 않은 동작을 할 수 있다.

 

🧐 how? 

→ NOT_EXISTS = [-1, -1] 를 변수로 정의해둔다. 

 

✔︎ 중요한 이유, +추가

- 초기 상태를 일관되게 관리할 수 있다. 

+ 리스트 객체는 가변성이 있어서 다른 부분에서 참조가 변경될 가능성이 있지만, 튜플이나 NOT_EXISTS와 같이 불변 객체로 초기 상태를 정의하면 더 안전하게 사용할 수 있다. (이때 튜플로 사용할거면 best_pos 도 튜플 형식으로 일관되게 사용해야함)

 

[코드]

1. 상하좌우로 이동할 수 있는 칸이라고 했으니, BFS를 사용해준다. (import deque) 

from collections import deque

n, k = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
r, c = map(int, input().split())

visited = [[False] * n for _ in range(n)]

q = deque()

def bfs():

    while q:
        cx, cy = q.popleft()  # cx, cy: 현재 위치

        target = arr[cx][cy]
        # 상 하 좌 우
        dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]
 		
        # 이동할 수 있는 칸을 탐색하며 이동 가능한 칸은 큐에 넣어주고 방문 표시를 한다. 
        for dx, dy in zip(dxs, dys):
            nx, ny = cx + dx, cy + dy

            if can_go(nx, ny, target):
                q.append((nx, ny))
                visited[nx][ny] = True

 

 

2. 이동 조건 설정

- 격자 내, 방문하지 않은 칸, 현재 위치의 칸 숫자보다 작을 것

def in_range(x, y):
    return 0 <= x < n and 0 <= y < n


def can_go(x, y, target):
    return in_range(x, y) and not visited[x][y] and arr[x][y] < target

 

 

3. visited 배열 초기화

def initialize_visited():
	for i in range(n):
    	for j in range(n):
        	visited[i][j] = False

 

 

4. K번 만큼 움직이기

- need_update() : 이동 가능한 칸을 비교한다. (숫자, -행, -열 순으로)

- move() : 위치 값으로 bfs를 호출하고 방문 가능한 칸을 기록한 visited 배열을 돌면서, 우선순위를 비교해 위치를 이동한다. 

def need_update(best_pos, new_pos):
    # 첫 도달 위치
    if best_pos == NOT_EXISTS:
        return True

    bx, by = best_pos
    nx, ny = new_pos

    # 숫자, -행, -열 순으로 우선순위 비교
    return [arr[nx][ny], -nx, -ny] > [arr[bx][by], -bx, -by]


def move():
    global cur

    # 좌표가 바뀔 때마다 BFS 탐색을 하기 위한 초기화
    initialize_visited()

    # 좌표 바뀔 때마다 BFS 호출
    bfs()

    best_pos = NOT_EXISTS
    for i in range(n):
        for j in range(n):
            if not visited[i][j] or [i, j] == cur:
                continue

            new_pos = [i, j]
            # 갱신이 필요한 경우
            if need_update(best_pos, new_pos):
                best_pos = new_pos

    # 움직일 위치가 없다면 종료
    if best_pos == NOT_EXISTS:
        return False

    # 움직일 위치가 있다면 이동
    else:
        cur = best_pos
        return True


for _ in range(k):
    is_moved = move()

    # 움직이지 못했다면 바로 종료
    if not is_moved:
        break

fx, fy = cur
print(fx+1, fy+1)

 

 

(최종 코드)

from collections import deque

n, k = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
r, c = map(int, input().split())

cur = [r-1, c-1]  # 시작 위치
NOT_EXISTS = [-1, -1]  # 위치가 존재하지 않음

visited = [[False] * n for _ in range(n)]

q = deque()


def in_range(x, y):
    return 0 <= x < n and 0 <= y < n


def can_go(x, y, target):
    return in_range(x, y) and not visited[x][y] and arr[x][y] < target


def initialize_visited():
    for i in range(n):
        for j in range(n):
            visited[i][j] = False


def bfs():
    dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]

    cx, cy = cur
    visited[cx][cy] = True
    q.append((cx, cy))

    target = arr[cx][cy]

    while q:
        cx, cy = q.popleft()  # cx, cy: 현재 위치

        # 상 하 좌 우
        for dx, dy in zip(dxs, dys):
            nx, ny = cx + dx, cy + dy

            if can_go(nx, ny, target):
                q.append((nx, ny))
                visited[nx][ny] = True


def need_update(best_pos, new_pos):
    # 첫 도달 위치
    if best_pos == NOT_EXISTS:
        return True

    bx, by = best_pos
    nx, ny = new_pos

    # 숫자, -행, -열 순으로
    return [arr[nx][ny], -nx, -ny] > [arr[bx][by], -bx, -by]


def move():
    global cur

    # 좌표가 바뀔 때마다 BFS 탐색을 하기 위한 초기화
    initialize_visited()

    # 좌표 바뀔 때마다 BFS 호출
    bfs()

    best_pos = NOT_EXISTS
    for i in range(n):
        for j in range(n):
            if not visited[i][j] or [i, j] == cur:
                continue

            new_pos = [i, j]
            # 갱신이 필요한 경우
            if need_update(best_pos, new_pos):
                best_pos = new_pos

    # 움직일 위치가 없다면 종료
    if best_pos == NOT_EXISTS:
        return False

    # 움직일 위치가 있다면 이동
    else:
        cur = best_pos
        return True


for _ in range(k):
    is_moved = move()

    # 움직이지 못했다면 바로 종료
    if not is_moved:
        break

fx, fy = cur
print(fx+1, fy+1)