런타임 에러(IndexError)
반례를 찾기 전까진 "맞왜틀"을 호소했습니다. IndexError가 일어나는 이유를 몰랐거든요.. 하지만 검증 과정에서 문제가 있었습니다.
아래의 소스코드를 보면 필드를 벗어나는 경우를 검증하지 않습니다. BFS/DFS때 흔히 하는 0<=nx<n 이런 검증 말이죠.
그래서 런타임 에러가 발생했고 이를 조건문 검증 후 제출했지만 틀렸습니다가 떴네요. 아래에서 추가 설명하겠습니다.
else:#그냥 길인 경우
field[ny][nx]=2#그 자리에 머리를 넣어줌
field[ty][tx]=0#꼬리 있던 자리를 없애줌
for tdx,tdy in [[0,1],[1,0],[-1,0],[0,-1]]:#다음 몸통 자리를 찾음
ndx,ndy = tx+tdx,ty+tdy
if field[ndy][ndx]==2:#몸통을 찾았다면
tailq.append([ndx,ndy])#그 몸통이 꼬리가 된다.
break
q.append([nx,ny])틀렸습니다
지나다니는 길을 0 뱀의 머리를 빨간색 2, 꼬리를 파란색 2라고 가정하겠습니다.
아래 그림을 보시면 이해가 바로 되실까요?
| 2 | 2 | 2 | |||||||
| 2 | 2 | 2 | |||||||
| 2 | 2 | ||||||||
| 2 | 2 | ||||||||
런타임 에러의 소스코드를 보시게 되면 꼬리는 이어져 있는 몸통을 찾기 위해 상, 하, 좌, 우로 서칭을 하게 됩니다.
자 위의 경우 몸통과 머리가 모두 붙어 있을 때 이어진 몸통을 찾는 게 아니라 엉뚱한 곳을 찾게 되면서 꼬리의 위치가 꼬여버리는 문제가 생깁니다. 그래서 이 부분을 자각하고 리스트와 덱(Deque)을 대공사 했습니다.
문제 설명
'뱀 게임', '지렁이 게임'이라고도 합니다. 한 칸씩 이동하며 사과를 먹는 게임이죠.
사과를 먹으면 몸의 길이가 1씩 증가합니다. 단, 사과를 다 먹는다고 해서 게임이 끝나는 게 아니라 벽에 닿거나 자신의 몸통과 겹쳐 버리면 게임이 끝나는 구조입니다.
소스 코드
Python3
필드에 뱀(2), 사과(1), 길(0)을 따로 저장해 두고 뱀의 좌표(SNAKE)를 저장했습니다. 뱀의 좌표(SNAKE)는 머리와 꼬리만 움직이면 되는 구조이므로 끝 부분의 append, pop에 용이한 Deque을 사용했습니다.
drcControl 함수는 뱀의 방향 전환을 해주고 옳은 방향으로 direction을 수정해 주는 역할입니다.
i의 값이 튀어 indexerror를 만들기 전에 조건문으로 주어진 범위 내에서만 작동할 수 있도록 지정해 두었습니다.
풀고 나니 평소 풀던 DFS/BFS보다 정말 쉬웠던 문제인데, 게임 형태로 문제가 나오니 많이 당황했던 것 같습니다.
##########################################################
import sys
from collections import deque
# direction = [[0,1],[-1,0],[1,0],[0,-1]] #for BFS
input = sys.stdin.readline
def ip():return input().rstrip()
def lip():return list(ip())
def ips():return ip().split()
def ii():return int(input())
def mii():return map(int,ips())
def lmii():return list(mii())
##########################################################
n = ii()#보드의 크기
k = ii()#사과의 개수
field = [[0]*n for _ in range(n)]
for _ in range(k):
a,b = mii()
field[a-1][b-1]=1 #1은 사과
l = ii()#뱀의 방향 변환 횟수
turn = deque()
for _ in range(l):
a,b = ips()
turn.append([int(a),b])
turn = deque(sorted(turn,key=lambda x:x[0]))#시간순 정렬
def drcControl(direc,turnd):#현재 방향과 바꾸는 방향
s = [[1,0],[0,1],[-1,0],[0,-1]]
for i,[a,b] in enumerate(s):
if [a,b]==direc:
if turnd=='L':
if i==0:i=4
return s[i-1]
else:
if i==3:i=-1
return s[i+1]
def solve():
global k
direction = [1,0]#오른쪽이 기본 방향
field[0][0]=2
SNAKE = deque([[0,0]])#뱀 꼬리-몸통-머리 구조를 나타낸다.
move = 0
while SNAKE:
x,y = SNAKE[-1]#머리
if turn and turn[0][0]==move:#방향 전환 먼저
direction = drcControl(direction,turn[0][1])
turn.popleft()
dx,dy = direction
nx,ny = dx+x,dy+y
if 0>nx or nx>=n or 0>ny or ny>=n or field[ny][nx]>1:#엔딩 조건
return move+1
if field[ny][nx]==1:#사과를 만난 경우
field[ny][nx]=2#그 자리에 머리를 넣어줌
SNAKE.append([nx,ny])#우측에 좌표를 추가해서 머리를 갱신해줌
else:#그냥 길인 경우
field[ny][nx]=2#그 자리에 머리를 넣어줌
tx,ty=SNAKE.popleft()#꼬리를 빼준다.
field[ty][tx]=0#꼬리 있던 자리를 없애줌
SNAKE.append([nx,ny])#머리를 넣어준다.
move+=1#시간 증가
print(solve())Java8 (21.02.02 추가)
81~84줄 주석을 해제하면 뱀이 이동하는 모습을 볼 수 있습니다.
package boj3190;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
static class Pos{
int x,y;
Pos(int x,int y){
this.x = x;
this.y = y;
}
}
static class Move{
int move;
char direction;
public Move(int move, char direction) {
this.move = move;
this.direction = direction;
}
}
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int N,K,L;
static int dirX[] = {1,0,-1,0};//우하좌상
static int dirY[] = {0,1,0,-1};
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException{
st = new StringTokenizer(bf.readLine());
N = Integer.parseInt(st.nextToken());//필드수
int[][] field = new int[N][N];
st = new StringTokenizer(bf.readLine());
K = Integer.parseInt(st.nextToken());//사과
for(int i =0;i<K;i++) {
st = new StringTokenizer(bf.readLine());
field[Integer.parseInt(st.nextToken())-1][Integer.parseInt(st.nextToken())-1]=1;//사과는 1
}
Deque<Pos> snake = new ArrayDeque<Main.Pos>();//뱀 관리 꼬리-몸통-머리 순
snake.add(new Pos(0,0));//몸추가
field[0][0]=2;//뱀은 2
Deque<Move> query = new ArrayDeque<>();//정수X, 문자C
st = new StringTokenizer(bf.readLine());
L = Integer.parseInt(st.nextToken());//방향전환 횟수
for(int i =0;i<L;i++) {//쿼리삽입
st = new StringTokenizer(bf.readLine());
query.add(new Move(Integer.parseInt(st.nextToken()),st.nextToken().charAt(0)));
}
int cur_direction = 0;//오른쪽으로 스타트
int answer =0 ;
while(true) {
Move tmp = query.poll();
int move = 99999;//쿼리를 다 수행했더라도 뱀은 계속 움직여야함.
if(tmp != null)
move = tmp.move;
for(int i =answer;i<move;i++) {
//다음 이동되는 좌표
int nx = snake.peekLast().x+dirX[cur_direction];
int ny = snake.peekLast().y+dirY[cur_direction];
if(0<=nx && nx<N && 0<=ny && ny<N && field[ny][nx]!=2) {
if(field[ny][nx]==1) {//사과가있는 경우 몸을 늘린다.
field[ny][nx]=2;
snake.addLast(new Pos(nx,ny));//머리를 사과자리에.
}
else {//단순이동
Pos tmp2 = snake.pollFirst();//꼬리제거
field[tmp2.y][tmp2.x]=0;
snake.addLast(new Pos(nx,ny));//머리로이동
field[ny][nx]=2;
}
answer++;
// System.out.println("=================="+answer);
// for(int z =0;z<field.length;z++) {
// System.out.println(Arrays.toString(field[z]));
// }
}
else {//벽에 또는 몸통에 부딪히면 게임종료
System.out.println(answer+1);
return;
}
}
//움직인 이후 방향전환
if(tmp.direction=='D') {
cur_direction++;
if(cur_direction>3)cur_direction=0;
}
else if(tmp.direction=='L') {
cur_direction--;
if(cur_direction<0)cur_direction=3;
}
}
}
}