백준 3190 뱀 문제를 BFS 를 활용해서 해결하는 방법을 자세하게 설명드립니다. 네카라쿠배 코딩테스트를 통과하려면 꼭 암기하고 있어야 하는 알고리즘 문제들이 있습니다. 가장 기본적인 문제들은 평소에 여러 번 반복하여 연습해 두어야 시험에 합격하기가 쉬워집니다. 변수의 의미와 로직을 매우 상세하게 설명하였으니 꼭 집중하여 읽어보시기 바랍니다.
Table of Contents
백준 3190 뱀 문제 풀이의 알고리즘
백준 3190 뱀 문제를 처음에 접하면 넓이 우선 탐색 ( bfs ) 알고리즘을 적용하고 싶은 충동을 느끼게 됩니다. 몇 번의 시행 착오 끝에 또상님의 bfs 와 유사하지만 정확히 넓이 우선 탐색 알고리즘을 사용하지 않는 방법을 찾게 되었습니다.
입력
6
3
3 4
2 5
5 3
3
3 D
15 L
17 D
출력
9
원문의 자세한 문제 설명은 아래에서 확인해 보실 수 있습니다.
넓이우선탐색 적용하기
넓이우선탐색이라고 불리는 bfs 알고리즘은 트리 구조의 자료 구조에서 깊이 보다는 같은 레벨의 인접 노드들을 먼저 검색하는 방식을 의미합니다. 깊이우선탐색 알고리즘과 함께 가장 널리 사용되고 있습니다.
백준 3190 문제 핵심 요약
백준 3190 뱀 문제는 몇 초 안에 N x N 개의 board 에서 K 개의 사과가 존재하고 있고 L 개의 이동 방향 전환 점이 존재할 때 모든 보드를 이동하다가 동작이 완료되는 시간을 구하는 문제입니다.
핵심은 BFS( ) 함수를 작성하여 사과가 위치해있는 좌표를 파악하고 방향 전환 지점에서 반시계 방향 또는 시계 방향으로 회전하도록 방향을 전환시켜 주는 로직을 코드로 작성하는 것입니다. 블로거 또상님의 코드를 공부하면서 제가 이해가 되지 않는 내용들 추가하여 상세하게 작성한 자료임을 말씀드립니다.
import sys
from collections import deque
def bfs():
head=(1,1)
body=[(1,1)]
time=0
board[1][1]=2
dir=0
direction=((0,1),(1,0),(0,-1),(-1,0))
#t, d는 move 리스트의 이중 배열의 원소들입니다.
for t,d in move:
for i in range(t):
x,y=head
nx=x+direction[dir][0]
ny=y+direction[dir][1]
ntime=time+1
#뱀이 벽을 만나거나 자기 자신에게 속한 블록으로 이동했는지 점검하기 위해서 board[nx][ny]의 값을 9 또는 2인지 여부를 확인합니다.
#일반적으로 bfs 알고리즘을 코딩할 때 반복 구문내에서 사용하는 x좌표와 y 좌표를 nx, ny 와 같은 notation으로 표현합니다.
if board[nx][ny]==9 or board[nx][ny]==2:
return ntime
#아래 구문이 사실상 백준 3190 문제의 핵심 구문입니다.
#뱀의 머리 좌표에 해당하는 (nx,ny)를 head에 저장하고 body 리스트에 해당 head 좌표 데이터셋을 입력해준다는 발상을 하기가 어려웠습니다.
# C++, C 프로그래밍에 비해서 python 이 좌표 데이터셋을 한번에 입력할 수 있어서 편리한 것 같습니다.
#아직 C 프로그래밍에 익숙해서 발상의 전환을 하기가 쉽지는 않습니다.
head=(nx,ny)
body.append(head)
time=ntime
# 아래 구문도 생각해 내기가 참 어려웠습니다.
# 아래 코드가 없으면 뱀의 머리는 사과 좌표로 이동하는데 뱀의 꼬리 지점이 지워지지 않고 남아있게 됩니다.
#뱀의 꼬리 좌표를 파악하기 위해서 body.pop(0) 로 마지막에 큐에 입력한 좌표 데이터셋을 꺼내는 발상을 하지 못하여 어려웠습니다.
# 꼬리에 해당하는 좌표 데이터셋을 확보한 후에는 해당 board[ 꼬리 x좌표][ 꼬리 y 좌표 ] = 0 으로 설정하여 board[ ][ ] 에서 꼬리의 흔적을 지워줍니다.
if board[nx][ny]!=1:
tail=body.pop(0)
print(tail)
board[tail[0]][tail[1]]=0
board[nx][ny]=2
dir=(dir+1)%4 if d=='D' else (dir -1)%4
return -1
#터미널에서 입력받은 값들이 내가 만든 리스트에 정확하게 입력되고 있는지 확인하기 위해서 중간 중간에 print( ) 구문을 넣어서 직접 프린트해서 확인하는 작업을 거쳐야 합니다.
readl=sys.stdin.readline
N=int(readl())
#print(f"N: {N}")
K=int(readl())
#print(f"K: {K}")
board=[[9] + [0]*N+ [9] if 1<=i <=N else [9]*(N+2) for i in range(N+2)]
for i in range(K):
x,y=map(int,readl().split())
#print(f"x:{x}, y:{y}")
board[x][y]=1
#print(board)
L=int(readl())
#print(f"L:{L}")
move=list()
moves = [readl().split() for _ in range(L)]
move = []
move.append([int(moves[0][0]), moves[0][1]])
for i in range(1, L):
move.append([int(moves[i][0]) - int(moves[i - 1][0]), moves[i][1]])
move.append([N, 'X'])
print(bfs())백준 3190 뱀 문제 풀이 발상의 전환
백준 3190 뱀 문제에서 주어지는 데이터 중에서 (시간, 방향전환하는 거리) 를 활용할 때 문제에서 주어지는 값을 그대로 사용하면 문제가 해결이 되지 않고 복잡해 집니다.
move[ ][ ] 라는 이중 배열 형태의 리스트를 생성하여 뱀이 t 초 후에 반시계 방향(‘D’) 와 시계방향(‘L’)을 고려하여 board[ ][ ] 의 어느 지점에 위치해 있는지 파악합니다.
move[x좌표][y좌표] 형태로 입력하게 됩니다. 문제의 입력에서 주어지는 거리 d는 과거로 부터 이동한 누적된 거리를 뜻합니다. 현재 시점과 다음번 시점까지 이동하는 거리를 구하려면 ” move[t 시점 x좌표][0] – move(t-1 시점 x좌표 )][0] ” 를 계산해야 합니다.
move[ i ][ ] 표현 식에서 두번째 원소는 x 좌표와 y 좌표를 지정하는 인덱스입니다. move[ i ][ 0 ] 은 x 좌표를 의미하고 move[ i ][ 1 ] 은 y 좌표를 의미합니다.
moves=[move[i][0] - move[i-1][0] for i in range(L)]위에서 moves[ ] 라는 리스트는 x 좌표값들 간의 차이값 만을 모아둔 리스트입니다. moves[ ] 에 저장된 차이값들을 다시 move[i] 리스트의 x 값인 move[ i ] [x] 에 집어넣어서 값을 업데이트 하기 위함입니다. 이렇게 차이값으로 변경해두지 않으면 뱀이 이동하면서 각 시간 구간마다 이동하는 길이를 파악할 수 없기 때문입니다.
move[ i ][ 0 ] = move[ moves[ i ]][ 0 ]
move[ i ][ 1 ] = move[ moves[ i ]][ 1 ]위의 코드를 해석하자면 move[ i ][ 0 ] 은 뱀의 x 좌표를 의미하고 move[ i ][ 1 ] 은 y 좌표를 의미합니다. 뱀의 x 값인 move[ i ][ 0 ] 은 move[moves[ i ]][0] 값으로 업데이트 됩니다. 또한, 뱀의 y 값인 move[ i ][ 1 ] 은 move[moves[ i ][ 1 ]] 값으로 업데이트 되게 됩니다.
지금까지 move[ i ] [ 0 ] 값을 업데이트하는 방법을 알아보았습니다. 이번에는 입력 값으로 L 개의 행에서 입력되는 move[ ][ ] 값들을 for 문을 이용해서 L 번 반복하여 입력 받는 방법을 알아보겠습니다.
첫 번째 원소인 (0,0)에는 원래 들어있던 값을 수동으로 입력해줍니다.# move[ ][ ] 리스트의 (0,0) 원소에 값을 넣는 방법으로써 append( ) 메서드를 사용합니다. 이때, moves[ ][ ] 리스트는 move[ ][ ] 리스트와 서로 다른 리스트임을 유의합니다.
move.append( moves[0][0] , moves[0][1] )지금부터 L 개의 행으로 부터 입력받은 데이터 셋을 move라는 리스트에 입력하는 구문입니다.
for i in range(L):
move.append( moves[ i ][ 0 ] - moves[ i - 1][0], move[ i ][ 1 ] ) 위 코드들을 이해하실 때에 주의 깊게 살펴보셔야 합니다. 거듭 말씀드리지만 moves[ ][ ] 리스트와 move[ ][ ] 리스트는 서로 다른 리스트임을 인지하셔야 합니다. 그리고, move[ i ][ 1 ]은 뱀이 방향을 전환하는 지점의 y 좌표값을 의미합니다.
for 문은 i 값이 1 부터 시작해서 L-1 번째 원소까지 반복됩니다. 가장 마지막 원소인 move[L][0] 값은 for 문에서 입력해 주지 않기 때문에 아래 코드와 같이 별도로 L 번째 원소를 채워주는 코드를 추가 작성해 주어야 합니다.
move.append( N, 'X' )마치며
백준 3190 뱀 문제를 BFS 알고리즘과 유사하게 전개하여 해결하는 방법을 자세하게 분석해 보았습니다. 네카라쿠배 코딩 테스트를 준비하면서 가장 기본적인 로직을 학습하기에는 적당한 수준의 코딩 문제입니다.
평소에 코딩 공부를 할 때에는 시간의 제한이 없어서 이런 저런 아이디어를 print( ) 로 찍어보면서 디버깅 할 시간이 충분히 주어지지만 실제 시험장 에서 3시간 안에 3문제에서 4문제를 해결하려면 시간이 무척 부족합니다.
코딩 공부를 시작한 지 벌써 6개월이 다 되어가는데 아직도 기본적인 알고리즘 코딩이 몸에 익지 않아서 걱정입니다. 다음에는 가장 알고리즘 코딩의 가장 기본이 되는 BFS 문제를 또 자세히 다뤄보도록 하겠습니다.