168. 뱀
1) 어떤 전략(알고리즘)으로 해결?
- deque!!
2) 코딩 설명
- 동서남북 구현 * (dfs , bfs에 나오는 것)
<내 풀이>
from collections import deque
import sys
#내가 바라보고 있는 방향
loc = [[-1,0], [0,1], [1,0], [0,-1]]
#북->R->동->R-남->R->서 순서
#R들어오면 loc[present+1]
#L들어오면 loc[present-1]
####################################################################
n = int(sys.stdin.readline().rstrip())
mapp = list([[0]*n for _ in range(n)]) #n*n map 만들기
####################################################################
k = int(sys.stdin.readline().rstrip()) #사과의 수
for i in range(k) :
r,c = map(int,sys.stdin.readline().rstrip().split())
mapp[r-1][c-1]=1 #사과 표시
####################################################################
l = int(sys.stdin.readline().rstrip())
save=[] #시간, 방향 저장할 리스트
for i in range(l) :
sec, lr = list(sys.stdin.readline().rstrip().split())
save.append([int(sec),lr])
####################################################################
sec=0
now=1 # 처음에 바라보는 방향이 동쪽 (loc의 인덱스)
row=0 #스네이크의 현재 위치 (row)
col=0 #스네이크의 현재 위치 (colimn)
tmprow=0
tmpcol=0
snake=deque() #스네이크의 몸통이 담겨있는 위치를 표시할 곳!
snake.append([0,0]) #처음 위치 초기화
while True :
# print("sec : ", sec)
# print(snake)
# for i in range(n):
# print(mapp[i])
sec+=1
if save and save[0][0]<sec :#초가 지나면 방향 바꾸기
if save[0][1] == "L" : #왼쪽 -1
now-=1#동이면 북쪽으로 갱신
if(now<0) : now+=4
else :
now+=1#동이면 남쪽으로 갱신
if(now>3) : now-=4
save.pop(0) #방향 바꾸고 나서 이 방향은 반영했으니 없애주기
#현재 위치 모의 갱신 (1초에 방향 기준으로, 한칸 이동)
tmprow+=loc[now][0]
tmpcol+=loc[now][1]
if [tmprow,tmpcol] in snake : #자기 몸통에 부딪히면
break
elif (tmpcol<n and tmpcol>-1) and (tmprow<n and tmprow>-1) : #몸통 아니고 벽 아니면
col=tmpcol #진짜 위치 갱신
row=tmprow
snake.append([row,col]) #뒤에다가 더하기
else :# 만약 갱신한 값이 벽이라면? (벽은 인덱스가 )
break
####################################################################
#갱신했는데 그곳의 사과 여부에 따라 꼬리 없앨지 말지 결정됨,
if mapp[row][col] != 1 : #사과 없다면 뒤의 꼬리 없애기
snake.popleft() #맨 처음에 있던 애(==꼬리, 큐 맨 앞) 는 삭제
else : #사과라면 사과 먹고 꼬리 냅두기 !
mapp[row][col] = 0
print(sec)
<내 틀렸던 풀이, 문제점>
from collections import deque
import sys
#내가 바라보고 있는 방향
loc = [[-1,0], [0,1], [1,0], [0,-1]]
#북->R->동->R-남->R->서 순서
#R들어오면 loc[present+1]
#L들어오면 loc[present-1]
####################################################################
n = int(sys.stdin.readline().rstrip())
mapp = list([[0]*n for _ in range(n)]) #n*n map 만들기
####################################################################
k = int(sys.stdin.readline().rstrip()) #사과의 수
for i in range(k) :
r,c = map(int,sys.stdin.readline().rstrip().split())
mapp[r-1][c-1]=1 #사과 표시
####################################################################
l = int(sys.stdin.readline().rstrip())
save=[] #시간, 방향 저장할 리스트
for i in range(l) :
sec, lr = list(sys.stdin.readline().rstrip().split())
save.append([int(sec),lr])
####################################################################
sec=0
now=1 # 처음에 바라보는 방향이 동쪽 (loc의 인덱스)
row=0 #스네이크의 현재 위치 (row)
col=0 #스네이크의 현재 위치 (colimn)
tmprow=0
tmpcol=0
snake=deque() #스네이크의 몸통이 담겨있는 위치를 표시할 곳!
snake.append([0,0]) #처음 위치 초기화
#######################################################################
while True :
# print("sec : ", sec)
# print(snake)
# for i in range(n):
# print(mapp[i])
sec+=1
if save and save[0][0]<sec :#초가 지나면 방향 바꾸기
if save[0][1] == "L" : #왼쪽 -1
now-=1#동이면 북쪽으로 갱신
if(now<0) : now+=4
else :
now+=1#동이면 남쪽으로 갱신
if(now>3) : now-=4
save.pop(0) #방향 바꾸고 나서 이 방향은 반영했으니 없애주기
#현재 위치 모의 갱신 (1초에 방향 기준으로, 한칸 이동)
tmprow+=loc[now][0]
tmpcol+=loc[now][1]
if [tmprow,tmpcol] in snake : #자기 몸통에 부딪히면
break
elif tmpcol<n and tmpcol>-1 and tmprow<n and tmpcol>-1 : #몸통 아니고 벽 아니면
col=tmpcol #진짜 위치 갱신
row=tmprow
snake.append([row,col]) #뒤에다가 더하기
else :# 만약 갱신한 값이 벽이라면? (벽은 인덱스가 )
break
####################################################################
#갱신했는데 그곳의 사과 여부에 따라 꼬리 없앨지 말지 결정됨,
if mapp[row][col] != 1 : #사과 없다면 뒤의 꼬리 없애기?
snake.popleft() #맨 처음에 있던 애(==꼬리) 는 삭제
else :
mapp[row][col] = 0
print(sec)
-
46% 에서 틀린다! why!??
-
https://www.acmicpc.net/board/view/56469 (반례들 사랑합니다 ㅠㅠ 흑흑) 에서 제시해주신 테케 중 5번 테케에서 잘못 나온다! 이것은 사과처리를 잘못 해주었기 때문이라고 한다, 근데 나는 사과 잘 제거했는걸,,?
-
내가 틀린 테케 => 답은 237인데, 251 나온다
35
28
21 2
22 23
3 5
34 30
29 31
3 28
20 12
27 26
31 7
5 10
21 10
19 2
15 23
4 23
3 19
3 35
13 30
30 30
23 27
32 17
22 24
8 27
4 8
30 18
15 28
22 29
28 5
16 33
20
27 D
61 L
68 L
100 L
133 L
160 L
165 D
168 D
170 D
182 D
206 D
207 D
214 D
215 D
216 L
237 D
240 D
241 L
251 D
252 D-
문제 발견~
-
나는 이렇게 -1이 되면 멈추게 해놨는데 안 멈춘다;;
(아래가 조건 건 부분)
-
에,,,네 안녕하세요? 전 멍청이입니다 ^^ ㅜ
ㅋㅋㅋㅋㅋㅋㅋㅋㅋ tmprow를 tmpcol이라 써놨네요? 하핫
ㅋㅋㅋㅋ위에서 캡처하고 당당하게 왜 저래!! 하다가 ㅋㅋㅋㅋㅋ 알아챘음
저 아이를 tmprow로 바꿔주자
<반성 점>
- 사소한 데서도 꼼꼼히 검토하자!
<배운 점>
- 이번에 로직을 탄탄히 설계하고 (약 2~30분) 그대로 코드로 구현했더니, 바로 통과가 돼버려서 너무 감격스러웠다. 앞으로도 로직을 튼튼히 해야지
