[알고리즘|파이썬] 백준 13901 로봇
문제 링크: https://www.acmicpc.net/problem/13901
📌 문제 탐색하기
시간 제한: 1초
메모리 제한: 256 MB
📌 풀이하기
로봇의 조건
- 로봇은 사용자가 지정한 방향을 일직선으로 움직인다.
- 이동 중 벽이나 방문한 지역, 장애물을 만날 경우 로봇은 사용자가 지정한 다음 방향으로 움직인다.
- 사용자가 지정한 다음 방향이 없다면 맨 처음 방향으로 돌아가서 위의 과정을 반복한다.
- 로봇이 움직일 수 없을 경우 동작을 멈춘다.
예제 1.
방 크기가 3* 3이고
장애물이 (1, 0)에 있으며
시작 위치는 (1,1)
해빈이가 지정한 방향이 (상, 하, 좌, 우) 일 때,
로봇의 마지막 위치는 (0, 0)이다.
1. 시작: (1, 1)
2. [상] 이동: (0, 1)
3. 벽을 만났으므로 [하]로 이동 -> (1, 1)는 이미 방문했으므로 다음 방향으로 넘어감 -> [좌]로 이동 : (0, 0)
4. 벽을 만났으므로 [우]로 이동 -> (0, 1)은 이미 방문 했으므로 다음 방향으로 넘어감 -> [상] 은 벽이므로 이동 불가. 다음 방향으로 넘어감 -> [하] 는 장애물이 있으므로 이동 불가. 다음 방향으로 넘어 감 -> [좌] 는 벽이므로 이동 불가. 다음 방향으로 넘어감 -> 더이상 움직일 수 없으므로 종료.
그러므로 로봇의 이동은 (1, 1) -> (0, 1) -> (0, 0)이 되고, 마지막 위치는 (0, 0)이 된다.
🤖 로봇을 어떻게 움직이게 할 것인가?
- 로봇은 사용자가 지정한 방향을 일직선으로 움직인다.
- 이동 중 벽이나 방문한 지역, 장애물을 만날 경우 로봇은 사용자가 지정한 다음 방향으로 움직인다.
- 사용자가 지정한 다음 방향이 없다면 맨 처음 방향으로 돌아가서 위의 과정을 반복한다.
- 로봇이 움직일 수 없을 경우 동작을 멈춘다.
로봇의 조건을 그대로 코드로 옮겨야한다.
상하좌우를 [(-1, 0), (1, 0), (0, -1), (0, 1)] 로 변환할 수 있다.
또한 이미 방문한 지역은 갈 수 없으므로 방문한 위치를 따로 기록을 해주어야한다.
📌 코드 설계하기
1. 방 크기 입력 및 초기화
2. 장애물 개수 k 입력 후, k번 반복하여 장애물 위치를 입력받아 room에 1로 표시
3. 로봇 시작 위치 설정: room[sr][sc] = 1로 방문 표시
4. 이동 방향 입력 및 설정
- 이동 방향 순서를 리스트(seq)로 입력받음
- direction = [(-1, 0), (1, 0), (0, -1), (0, 1)] // 상하좌우
5. 로봇 이동 시뮬레이션
- while 문을 사용하여 로봇이 이동할 수 없을 때까지 반복
- 이동 가능하면 가야하는 방향으로 이동, 이동한 위치는 1로 채우기
- 이동 불가하면 다음 방향으로 넘어가기
6. 최종 위치 출력 : sr, sc 값을 출력하여 로봇이 멈춘 위치를 표시
📌 시도 회차 수정 사항
1회차: 런타임 에러 (IndexError)
# 변경 전
if room[sr+i][sc+j] == 1 or sr+i < 0 or sr+i >= r or sc+j < 0 or sc+j >= c :
# 변경 후
if sr+i < 0 or sr+i >= r or sc+j < 0 or sc+j >= c or room[sr+i][sc+j] == 1 :sr+i, sc+j가 각각 r, c를 넘는 경우 room[sr+i][sc+j] 조건을 if 문에서 먼저 확인하게 되면 index 에러가 날 수 있다.
그러므로 먼저 배열 조건에 넘지 않는지를 확인한 후에 배열 조회를 하도록 순서를 바꿔주면 된다.
📌 정답 코드
r, c = map(int, input().split())
room = [[0 for _ in range(c)] for _ in range(r)]
k = int(input())
for _ in range(k):
br, bc = map(int, input().split())
room[br][bc] += 1
sr, sc = map(int, input().split())
room[sr][sc] = 1 # 첫 위치 방문 표시
seq = list(map(int, input().split()))
direction = [(0, 0), (-1, 0), (1, 0), (0, -1), (0, 1)] # [0]은 안쓰는 값, 상하좌우
flag = True
idx = 0
count = 0
while flag:
seq_now = seq[idx]
now = direction[seq_now]
i, j = now[0], now[1]
if sr+i < 0 or sr+i >= r or sc+j < 0 or sc+j >= c or room[sr+i][sc+j] == 1 : # 다음을 못가는 경우
idx += 1 # 다음 순서로 넘김
idx %= len(seq)
count += 1
if count == 5:
flag = False
else: # 다음을 갈 수 있는 경우
sr = sr+i
sc = sc+j
room[sr][sc] = 1
count = 0
print(sr, sc)