1. 뱀
- 난이도
- 중 / 골5
- 풀이 시간
- 40분
- 시간 제한
- 1초
- 메모리 제한
- 128 MB
- 출처
A. 문제
- 중 / 골5
- 40분
- 1초
- 128 MB
위 백준 사이트에 접속하여 문제를 확인해주세요.
B. 내 답안
a. 1차 시도 (성공 / 시간초과)
# 백준 3190번 문제
from collections import deque
n = int(input())
# 게임 맵
game_map = [[0] * (n+1) for _ in range(n+1)]
# 사과 관련
apple_count = int(input())
apple_pos = []
for i in range(apple_count):
# apple_pos.append(list(map(int, input().split())))
x, y = list(map(int, input().split()))
game_map[x][y] = 2
# 뱀의 방향 회전 관련
snake_d_count = int(input())
# snake_d_info = deque()
snake_d_info = []
for i in range(snake_d_count):
temp = list(input().split())
# snake_d_info.append([int(temp[0]), temp[1]])
snake_d_info.append([int(temp[0]), temp[1]])
# 뱀의 현재 방향
d = 0
# 뱀의 현재 방향에 따라 앞으로 갈 방향을 지정 (x - ds[d][0] 이런 식으로)
ds = [(0,1), (1,0), (0,-1), (-1,0)]
# 현재 뱀의 위치
pos = [1, 1]
# 뱀의 길이
snake_length = 1
# 게임 진행 시간
time = 0
# 머리 위치 저장하는 큐 // 생각해보니 머리는 스택으로 해도 될 듯
# 루프가 반복될 때마다 머리에 저장된 데이터가 추출됨.
# 머리는 시간이 지날때마다 다음 위치가 큐에 추가됨.
q_head_pos = deque()
q_head_pos.append(pos)
# 꼬리 위치를 저장하는 큐
# 다음 위치에 사과가 없으면 pop.# 사과가 있으면 그냥 반복해서 꼬리 위치 보전
q_tail_pos = deque()
q_tail_pos.append(pos)
# 게임 시작시 뱀위 위치는 (맨위, 맨좌) = (1, 1)라서 map을 채우고 시작함.
game_map[pos[0]][pos[1]] = 1
# 방향 전환에 필요한 d를 가리키는 pointsnake_d_info_point = 0
while True:
x, y = q_head_pos.popleft()
# 방향전환에 필요한 시간이 되면 방향 전환
if len(snake_d_info) > snake_d_info_point:
if time == snake_d_info[snake_d_info_point][0]:
if snake_d_info[snake_d_info_point][1] == "D":
d = (d + 1) % 4
else:
d = (d - 1) % 4
# d_info_time, d_info_move = snake_d_info.popleft()
snake_d_info_point += 1
# 시간을 1초 증가시키고 다음 좌표를 탐색함.
time += 1
dx = x + ds[d][0]
dy = y + ds[d][1]
# 다음 좌표가 벽이거나 뱀의 몸통이면 게임 끝
if dx < 1 or dx > n or dy < 1 or dy > n:
break
if game_map[dx][dy] == 1:
break
# 다음 좌표가 사과면 꼬리 유지, 사과가 아니면 꼬리 제거하고 맵 원상복구
if game_map[dx][dy] != 2:
tx, ty = q_tail_pos.popleft()
game_map[tx][ty] = 0
# 여기까지 왔으면, 장애물들은 다 통과한거니 맵을 채움.
game_map[dx][dy] = 1
# 다음 위치를 머리와 꼬리에 집어넣음.
q_head_pos.append([dx, dy])
q_tail_pos.append([dx, dy])
print(time)
# 1시간 45분 / Pass
b. 2차 시도 (성공 / 시간초과)
from collections import deque
n = int(input())
k = int(input())
# 맵은 0으로 표시
game_map = [[0]*(n+1) for _ in range(n+1)]
# 사과는 2로 표시
for i in range(k):
x, y = list(map(int, input().split()))
game_map[x][y] = 2
l = int(input())
snake_distance = []
# 이것도 큐로 만들면 더 효율적일꺼 같음.
# 밑에 for문을 쓰지 않아도 되니까
for i in range(l):
time, d = list(input().split())
time = int(time)
snake_distance.append((time, d))
# 뱀의 머리는 스택 / 굳이 스택이 아니여도 됨. 입력 -> 삭제를 반복하니까.
# 뱀의 꼬리는 큐
snake_head = [1, 1]
snake_tail = deque()
snake_tail.append((1, 1))
# 동남서북
# 처음 바라보는 방향이 오른쪽
# 오른쪽에서 오른쪽으로 방향을 바꾸면 남
# 왼쪽으로 방향을 바꾸면 북
distance = [(0, 1), (1, 0), (0, -1), (-1, 0)]
snake_d = 0
time = 0
# 게임은 종료조건을 만나기 전까지 끝나지 않음
while True:
x, y = snake_head
# 뱀의 방향은 게임 시작 시간으로부터 X초가 끝난 뒤에 회전한다.
# 현재 시간과 뱀이 방향 바꾸는 시간을 비교하여 조건이 맞으면 방향을 바꿈
for s in snake_distance:
s_time, s_d = s
if s_time == time:
if s_d == "D":
snake_d = (snake_d + 1) % 4
elif s_d == "L":
snake_d = (snake_d - 1) % 4
# 시간을 추가함.
# 현재 시간(Line 51 앞부분)이 0일때, dx 부분의 시간(Line 57 뒷부분)은 1임.
time += 1
# 다음 위치를 예상해본다.
dx = x + distance[snake_d][0]
dy = y + distance[snake_d][1]
# 뱀이 벽에 부딪쳤을때
if dx < 1 or dx > n or dy < 1 or dy > n:
break
# 뱀이 자기 몸과 부딪쳤을 때
if game_map[dx][dy] == 1:
break
# 다음 위치에 사과가 없을 때
if game_map[dx][dy] != 2:
# 꼬리를 삭제하고 맵에서도 뱀의 꼬리 부분을 지운다.
tx, ty = snake_tail.popleft()
game_map[tx][ty] = 0
# 다음 위치에 사과가 있을 때
elif game_map[dx][dy] == 2:
pass
# 사과가 있든 없든, 다음 위치는 1(뱀)로 채움
# 뱀의 머리(스택), 꼬리(큐)에도 다음 위치를 추가함.
game_map[dx][dy] = 1
snake_head = [dx, dy]
snake_tail.append((dx, dy))
print(time)
# 43분 32초
c. 회고
내 풀이
- 그냥 지문의 조건대로 구현했다.
반성
- 시간이 조금 걸렸다.
- 시간에 대한 문제 때문인데, (1,1)에서 뱀이 시작할 때를 1초로 잡고 구현했었다.
- 문제는
매 초마다 이동, 게임 시작 시간으로부터 X초가 끝난 뒤라고 제시되어 있다.
- 그래서 (1,1)의 시작 시간은 0초, 종료 시간은 1초가 된다. 그리고 1초가 지났으니 이동하게 된다. (이 부분은 아래 그림으로 설명하겠다.)
결론
- 순서대로 차근차근 구현하면 되는데, 너무 뒤죽박죽으로 생각했다.
- 앞으로 이런 좌표 구현 문제는, 현재 위치와 다음 위치를 고려해서 구현해야겠다.
- 다음 위치는 게임 종료 조건(제한 조건)을 검사하고 queue에 넣어주는 방식으로.
C. 문제 해설
이해한 내용을 바탕으로 작성했습니다.
# 백준 3190번 문제
from collections import deque
n = int(input())
# 게임 맵
game_map = [[0] * (n+1) for _ in range(n+1)]
# 사과 관련
apple_count = int(input())
apple_pos = []
for i in range(apple_count):
# apple_pos.append(list(map(int, input().split())))
x, y = list(map(int, input().split()))
game_map[x][y] = 2
# 뱀의 방향 회전 관련
snake_d_count = int(input())
# snake_d_info = deque()
snake_d_info = []
for i in range(snake_d_count):
temp = list(input().split())
# snake_d_info.append([int(temp[0]), temp[1]])
snake_d_info.append([int(temp[0]), temp[1]])
# 뱀의 현재 방향
d = 0
# 뱀의 현재 방향에 따라 앞으로 갈 방향을 지정 (x - ds[d][0] 이런 식으로)
ds = [(0,1), (1,0), (0,-1), (-1,0)]
# 현재 뱀의 위치
pos = [1, 1]
# 뱀의 길이
snake_length = 1
# 게임 진행 시간
time = 0
# 머리 위치 저장하는 큐 // 생각해보니 머리는 스택으로 해도 될 듯
# 루프가 반복될 때마다 머리에 저장된 데이터가 추출됨.
# 머리는 시간이 지날때마다 다음 위치가 큐에 추가됨.
q_head_pos = deque()
q_head_pos.append(pos)
# 꼬리 위치를 저장하는 큐
# 다음 위치에 사과가 없으면 pop.# 사과가 있으면 그냥 반복해서 꼬리 위치 보전
q_tail_pos = deque()
q_tail_pos.append(pos)
# 게임 시작시 뱀위 위치는 (맨위, 맨좌) = (1, 1)라서 map을 채우고 시작함.
game_map[pos[0]][pos[1]] = 1
# 방향 전환에 필요한 d를 가리키는 pointsnake_d_info_point = 0
while True:
x, y = q_head_pos.popleft()
# 방향전환에 필요한 시간이 되면 방향 전환
if len(snake_d_info) > snake_d_info_point:
if time == snake_d_info[snake_d_info_point][0]:
if snake_d_info[snake_d_info_point][1] == "D":
d = (d + 1) % 4
else:
d = (d - 1) % 4
# d_info_time, d_info_move = snake_d_info.popleft()
snake_d_info_point += 1
# 시간을 1초 증가시키고 다음 좌표를 탐색함.
time += 1
dx = x + ds[d][0]
dy = y + ds[d][1]
# 다음 좌표가 벽이거나 뱀의 몸통이면 게임 끝
if dx < 1 or dx > n or dy < 1 or dy > n:
break
if game_map[dx][dy] == 1:
break
# 다음 좌표가 사과면 꼬리 유지, 사과가 아니면 꼬리 제거하고 맵 원상복구
if game_map[dx][dy] != 2:
tx, ty = q_tail_pos.popleft()
game_map[tx][ty] = 0
# 여기까지 왔으면, 장애물들은 다 통과한거니 맵을 채움.
game_map[dx][dy] = 1
# 다음 위치를 머리와 꼬리에 집어넣음.
q_head_pos.append([dx, dy])
q_tail_pos.append([dx, dy])
print(time)
# 1시간 45분 / Pass
b. 2차 시도 (성공 / 시간초과)
from collections import deque
n = int(input())
k = int(input())
# 맵은 0으로 표시
game_map = [[0]*(n+1) for _ in range(n+1)]
# 사과는 2로 표시
for i in range(k):
x, y = list(map(int, input().split()))
game_map[x][y] = 2
l = int(input())
snake_distance = []
# 이것도 큐로 만들면 더 효율적일꺼 같음.
# 밑에 for문을 쓰지 않아도 되니까
for i in range(l):
time, d = list(input().split())
time = int(time)
snake_distance.append((time, d))
# 뱀의 머리는 스택 / 굳이 스택이 아니여도 됨. 입력 -> 삭제를 반복하니까.
# 뱀의 꼬리는 큐
snake_head = [1, 1]
snake_tail = deque()
snake_tail.append((1, 1))
# 동남서북
# 처음 바라보는 방향이 오른쪽
# 오른쪽에서 오른쪽으로 방향을 바꾸면 남
# 왼쪽으로 방향을 바꾸면 북
distance = [(0, 1), (1, 0), (0, -1), (-1, 0)]
snake_d = 0
time = 0
# 게임은 종료조건을 만나기 전까지 끝나지 않음
while True:
x, y = snake_head
# 뱀의 방향은 게임 시작 시간으로부터 X초가 끝난 뒤에 회전한다.
# 현재 시간과 뱀이 방향 바꾸는 시간을 비교하여 조건이 맞으면 방향을 바꿈
for s in snake_distance:
s_time, s_d = s
if s_time == time:
if s_d == "D":
snake_d = (snake_d + 1) % 4
elif s_d == "L":
snake_d = (snake_d - 1) % 4
# 시간을 추가함.
# 현재 시간(Line 51 앞부분)이 0일때, dx 부분의 시간(Line 57 뒷부분)은 1임.
time += 1
# 다음 위치를 예상해본다.
dx = x + distance[snake_d][0]
dy = y + distance[snake_d][1]
# 뱀이 벽에 부딪쳤을때
if dx < 1 or dx > n or dy < 1 or dy > n:
break
# 뱀이 자기 몸과 부딪쳤을 때
if game_map[dx][dy] == 1:
break
# 다음 위치에 사과가 없을 때
if game_map[dx][dy] != 2:
# 꼬리를 삭제하고 맵에서도 뱀의 꼬리 부분을 지운다.
tx, ty = snake_tail.popleft()
game_map[tx][ty] = 0
# 다음 위치에 사과가 있을 때
elif game_map[dx][dy] == 2:
pass
# 사과가 있든 없든, 다음 위치는 1(뱀)로 채움
# 뱀의 머리(스택), 꼬리(큐)에도 다음 위치를 추가함.
game_map[dx][dy] = 1
snake_head = [dx, dy]
snake_tail.append((dx, dy))
print(time)
# 43분 32초
c. 회고
내 풀이
- 그냥 지문의 조건대로 구현했다.
반성
- 시간이 조금 걸렸다.
- 시간에 대한 문제 때문인데, (1,1)에서 뱀이 시작할 때를 1초로 잡고 구현했었다.
- 문제는
매 초마다 이동, 게임 시작 시간으로부터 X초가 끝난 뒤라고 제시되어 있다.
- 그래서 (1,1)의 시작 시간은 0초, 종료 시간은 1초가 된다. 그리고 1초가 지났으니 이동하게 된다. (이 부분은 아래 그림으로 설명하겠다.)
결론
- 순서대로 차근차근 구현하면 되는데, 너무 뒤죽박죽으로 생각했다.
- 앞으로 이런 좌표 구현 문제는, 현재 위치와 다음 위치를 고려해서 구현해야겠다.
- 다음 위치는 게임 종료 조건(제한 조건)을 검사하고 queue에 넣어주는 방식으로.
C. 문제 해설
이해한 내용을 바탕으로 작성했습니다.
from collections import deque
n = int(input())
k = int(input())
# 맵은 0으로 표시
game_map = [[0]*(n+1) for _ in range(n+1)]
# 사과는 2로 표시
for i in range(k):
x, y = list(map(int, input().split()))
game_map[x][y] = 2
l = int(input())
snake_distance = []
# 이것도 큐로 만들면 더 효율적일꺼 같음.
# 밑에 for문을 쓰지 않아도 되니까
for i in range(l):
time, d = list(input().split())
time = int(time)
snake_distance.append((time, d))
# 뱀의 머리는 스택 / 굳이 스택이 아니여도 됨. 입력 -> 삭제를 반복하니까.
# 뱀의 꼬리는 큐
snake_head = [1, 1]
snake_tail = deque()
snake_tail.append((1, 1))
# 동남서북
# 처음 바라보는 방향이 오른쪽
# 오른쪽에서 오른쪽으로 방향을 바꾸면 남
# 왼쪽으로 방향을 바꾸면 북
distance = [(0, 1), (1, 0), (0, -1), (-1, 0)]
snake_d = 0
time = 0
# 게임은 종료조건을 만나기 전까지 끝나지 않음
while True:
x, y = snake_head
# 뱀의 방향은 게임 시작 시간으로부터 X초가 끝난 뒤에 회전한다.
# 현재 시간과 뱀이 방향 바꾸는 시간을 비교하여 조건이 맞으면 방향을 바꿈
for s in snake_distance:
s_time, s_d = s
if s_time == time:
if s_d == "D":
snake_d = (snake_d + 1) % 4
elif s_d == "L":
snake_d = (snake_d - 1) % 4
# 시간을 추가함.
# 현재 시간(Line 51 앞부분)이 0일때, dx 부분의 시간(Line 57 뒷부분)은 1임.
time += 1
# 다음 위치를 예상해본다.
dx = x + distance[snake_d][0]
dy = y + distance[snake_d][1]
# 뱀이 벽에 부딪쳤을때
if dx < 1 or dx > n or dy < 1 or dy > n:
break
# 뱀이 자기 몸과 부딪쳤을 때
if game_map[dx][dy] == 1:
break
# 다음 위치에 사과가 없을 때
if game_map[dx][dy] != 2:
# 꼬리를 삭제하고 맵에서도 뱀의 꼬리 부분을 지운다.
tx, ty = snake_tail.popleft()
game_map[tx][ty] = 0
# 다음 위치에 사과가 있을 때
elif game_map[dx][dy] == 2:
pass
# 사과가 있든 없든, 다음 위치는 1(뱀)로 채움
# 뱀의 머리(스택), 꼬리(큐)에도 다음 위치를 추가함.
game_map[dx][dy] = 1
snake_head = [dx, dy]
snake_tail.append((dx, dy))
print(time)
# 43분 32초
내 풀이
- 그냥 지문의 조건대로 구현했다.
반성
- 시간이 조금 걸렸다.
- 시간에 대한 문제 때문인데, (1,1)에서 뱀이 시작할 때를 1초로 잡고 구현했었다.
- 문제는
매 초마다 이동,게임 시작 시간으로부터 X초가 끝난 뒤라고 제시되어 있다. - 그래서 (1,1)의 시작 시간은 0초, 종료 시간은 1초가 된다. 그리고 1초가 지났으니 이동하게 된다. (이 부분은 아래 그림으로 설명하겠다.)
- 문제는
결론
- 순서대로 차근차근 구현하면 되는데, 너무 뒤죽박죽으로 생각했다.
- 앞으로 이런 좌표 구현 문제는, 현재 위치와 다음 위치를 고려해서 구현해야겠다.
- 다음 위치는 게임 종료 조건(제한 조건)을 검사하고 queue에 넣어주는 방식으로.
C. 문제 해설
이해한 내용을 바탕으로 작성했습니다.
이해한 내용을 바탕으로 작성했습니다.
아래 그림을 보면 어떤 방식으로 구현해야하는지 감이 올 것이라 생각한다.
초보자는 손으로 그려보면서 해보는걸 추천한다.
a. 책 답안
python-for-coding-test/5.py at master · ndb796/python-for-coding-test (github.com)
참고문헌
[1] 나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년
[2] 3190번: 뱀 (acmicpc.net). Baekjoon. (accessed Sep 15, 2021)
Ghost