백준 13459 - 파이썬

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

13459번: 구슬 탈출

문제 풀이

상당히 어려운 문제였던거 같다. 처음에 풀이를 좀 하다가 모르겠어서 다른 사람의 블로그를 찾아봤다.

 

문제 풀의 핵심은 다음과 같다.

 

1. 빨간 공과 파란 공의 위치 변수를 각각 선언

2. 빨간 공이 먼저 탈출하게 된다면 print(1) 출력

3. 파란 공이 먼저 탈출하면 안 됨

4. 기존 BFS에서는 방향 리스트가 한번 움직일 때 큐에 추가되는 것도 동시에 이뤄졌다면, 이번에는 벽이나 탈출 구멍을 만나기 전까지 계속 뱡향 리스트를 더해주면 된다.

5. 계속 이동하며 이동한 거리를 더해주다가 벽을 만나면 한 칸 뒤로 이동함.

6. 10번 이내에 탈출해야 하기에 탈출 구멍을 만났을 때 반복문을 탈출해 주고, 10번 이내에 탈출한 것인지 확인

7. 4 ~ 6을 빨간 공, 파란 공 각각 작성해 주면 됨

8. 파란 공이 먼저 탈출시 무시하고 계속해야 됨(continue)

9. 만약 빨간 공과 파란 공의 위치가 같다면. 이동 거리가 더 많은 공이 더 늦게 출발한 것이기에 한 칸 뒤로 이동해야 함(공 하나다 한 칸 차지하므로 중복 x)

10. 4 ~ 9를 다 완료 후, 처음 방문했다면 큐에 새롭게 추가

11. 1 ~ 10까지가 한 사이클이므로, 한 사이클 종료 시 count + 1

12. 10회 초과하지 않았지만 10회 내에도 공이 탈출하지 못한다면 실패로 처리

 

이렇게가 코드를 작성하기 위해서 생각해야 할 것들이다. 아래는 위 내용을 코드로 옮긴 것이다.

 

코드

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

n,m = map(int,input().split())
graph = []
for i in range(n):
  graph.append(list(input()))
  for j in range(m):
    if graph[i][j] == 'R':
      rx,ry = i,j
    elif graph[i][j] == 'B':
      bx,by = i,j

dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(rx,ry,bx,by):
  q = deque()
  q.append((rx,ry,bx,by))
  visited = []
  visited.append((rx,ry,bx,by))
  count = 0
  while q:
    for _ in range(len(q)):
      rx,ry,bx,by = q.popleft()
      if count > 10:
        print(0)
        return
      if graph[rx][ry] == 'O':
        print(1)
        return
      for i in range(4):
        nrx,nry = rx,ry
        while True:
          nrx += dx[i]
          nry += dy[i]
          if graph[nrx][nry] == '#':
            nrx -= dx[i]
            nry -= dy[i]
            break
          if graph[nrx][nry] == 'O':
            break
        nbx,nby = bx,by
        while True:
          nbx += dx[i]
          nby += dy[i]
          if graph[nbx][nby] == '#':
            nbx -= dx[i]
            nby -= dy[i]
            break
          if graph[nbx][nby] == 'O':
            break
        if graph[nbx][nby] == 'O':
          continue
        if nrx == nbx and nry == nby:
          if abs(nrx -rx) + abs(nry - ry) > abs(nbx - bx) + abs(nby - by):
            nrx -= dx[i]
            nry -= dy[i]
          else:
            nbx -= dx[i]
            nby -= dy[i]
        if (nrx,nry,nbx,nby) not in visited:
          q.append((nrx,nry,nbx,nby))
          visited.append((nrx,nry,nbx,nby))
    count += 1
  print(0)
bfs(rx,ry,bx,by)

 

느낀 점

이번 문제를 풀면서 느낀 점은 여러 가지 조건을 고려해야 하고, 기존의 방식에서 살짝 달라지면 코드를 작성하는데 있어 굉장히 힘들어한다는 점이다. 이 힘들어 한다는 것은 어떤 변수를 선언하고 예외를 고려해줘야 할지 생각이 엉킨다는 것을 의미한다. 머릿속에서 어떻게 풀어야 할지 이제 느낌은 오지만 이것을 논리정연하게 표현하지는 못하는 거 같다.  간단한 문제인 경우에는 머리속에 떠오른 것을 바로 코드로 옮겨도 디버깅하는데 복잡하거나 많은 시간이 걸리지 않지만 이런 문제의 경우는 충분히 꼬이기 쉬운 거 같다. 이 부분을 발전시키기 위해서는 노트에다가 떠오른 생각을 정리하고, 문제를 풀면서 생각해야 할 핵심이 무엇일지 글로 정리하는 연습이 필요한 거 같다. 다음부터는 정리하면서 풀어봐야 되겠다.