카테고리 없음
[백준 14503] 로봇청소기 (구현,시뮬레이션)
- -
🍫문제
그냥 차근차근 조건에 따라서 구현하면 되는 문제였다.
이 문제는 2017년 상반기 삼성 그룹 오후 1번 문제이다. LG CNS기출과 유사한 문제이기도 하다.
추천 사이트에서 발견했는데,,,,,
결국 딜레마에 빠져 해결하지 못했다. 흑흑... 반성을 좀 해보자면
1. 어?쉽네? 하고 문제를 제대로 설계하지 않고 문제풀이에 뛰어들었다.->그러다보니 하드코딩의 늪에 빠짐...
2. 아직 재귀호출,반복문,조건문을 적절히 언제 써야하는지 잘 안잡혀 있는 느낌이다.. -> 컨디션 좋으면 잘풀리고, 안좋으면 이상한 길에 빠져버림(특히 재귀호출)
-> 실전 코테는 컨디션이 좋을 리가 없다는 거! 더 연습하자
+
골드의 벽은 높다
🍫풀이
로봇청소기의 동작 원리는 아래와 같다
1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우
2-1) 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면
-> 한 칸 후진한 후, 1번으로 돌아간다
2-2) 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면
->작동을 멈춘다
3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우
3-1) 반시계 방향으로 90도 회전한다.
3-1.1) 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우
-> 한 칸 전진한다.
->1번으로 돌아간다.
3-1.2) 바라보는 방향을 기준으로 앞쪽 칸이 청소되어 있는 경우
-> 바로 1번으로 돌아간다
기존 풀이 방식❌
처음에는 1->2->3 순으로 풀려고 했다. 그러다보니 코드가 복잡해진 것이,
- 2번 로직(주변 4칸 탐색)에서, 모든 방향을 한 번에 탐색해야 했기 때문에 불필요하게 많은 처리가 발생
- 또한, 3번 로직(반시계 방향으로 90도 회전 후 전진)에서, 이미 탐색한 방향에 대해 다시 탐색하는 상황이 발생하여 코드가 더 복잡해짐
결국, 2번과 3번에서 중복된 처리를 하게 되어 코드가 굉장히 복잡하고 더러워졌다......여기에서 딜레마에 빠짐..
최종 풀이 방식⭕
⭐ 그래서, 1)청소 → 4방향 탐색 → 3.1.1)이동 or 2.1) 후진 순으로 진행했다
이 방식에서는 4방향을 한 번만 탐색하고, 그 결과에 따라 이동 또는 후진을 결정하게 되어 코드가 훨씬 간결해졌다!
구체적인 로직을 살펴보자
1. now_clean 함수 : 현재 칸 청소
현재 칸이 청소되지 않은 경우, 그 칸을 청소하는 now_clean 함수를 구현했다.
def now_clean(row, col, lst):
global cnt
if lst[row][col] == 0: # 현재 칸이 청소되지 않았다면
lst[row][col] = 2 # 현재 칸을 청소 (2는 청소 완료 상태)
cnt += 1 # 청소한 칸의 수를 증가
해당 함수는 칸이 청소되지 않은 상태(0)라면, 해당 칸을 청소 완료 상태(2)로 바꾸고,
청소한 칸의 개수를 세는 cnt 변수를 증가시킨다.
2. around_check_and_action 함수 : 주변 4칸 탐색 -> 청소 여부에 따라, 다른 동작(전진 or 후진) 수행
현재 위치에서 반시계 방향으로 90도씩 회전하면서(for문) 주변 4칸을 탐색한다
-> 청소되지 않은 빈 칸(0)을 발견하면 그 방향으로 이동해 다시 같은 로직을 반복한다.(재귀호출)
⭐ 핵심은 재귀 호출을 통해 청소되지 않은 칸을 계속 탐색하는 것이었다!
청소할 수 있는 빈 칸이 없다면(for문을 다 돌았음에도, 재귀호출을 하지 않았다면)
다음으로, 후진하는 작업을 하게 된다
-> 4방향 모두 청소된 경우, 후진한다
⭐ 후진할 수 있는 공간이 벽이 아니라면 후진하고,
다시 around_check_and_action 함수를 호출해 청소를 이어간다.
후진할 수 없다면 작동이 종료된다
def around_check_and_action(row, col, sight, lst):
now_clean(row, col, lst) # 현재 칸 청소
for _ in range(4): # 4 방향 회전
new_sight = (sight + 3) % 4 # 반시계 방향으로 회전
nr = row + dr[new_sight]
nc = col + dc[new_sight]
if 0 <= nr < N and 0 <= nc < M :
if lst[nr][nc] == 0: # case1)청소되지 않은 빈 칸이 있을 때
around_check_and_action(nr, nc, new_sight, lst) #재귀호출
return
sight = new_sight # 다음 회전을 위해 방향 업데이트
# case2) 네 방향 모두 청소된 경우 => 후진
back_dir = (sight + 2) % 4 # 현재 방향의 반대 방향
nr = row + dr[back_dir]
nc = col + dc[back_dir]
if 0 <= nr < N and 0 <= nc < M and lst[nr][nc] != 1: # 벽이 아닐 때
around_check_and_action(nr, nc, sight, lst)
🍫전체 코드
# 상(북), 우(동), 하(남), 좌(서)
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
N, M = map(int, input().split())
r, c, sight = map(int, input().split())
room = [list(map(int, input().split())) for _ in range(N)]
cnt = 0
def now_clean(row, col, lst):
global cnt
if lst[row][col] == 0: # 현재 칸이 청소되지 않았다면
lst[row][col] = 2 # 현재 칸을 청소 (2는 청소 완료 상태)
cnt += 1
def around_check_and_action(row, col, sight, lst):
now_clean(row, col, lst) # 현재 칸 청소
for _ in range(4): # 4 방향 회전
new_sight = (sight + 3) % 4 # 반시계 방향으로 회전
nr = row + dr[new_sight]
nc = col + dc[new_sight]
if 0 <= nr < N and 0 <= nc < M :
if lst[nr][nc] == 0: # 청소되지 않은 빈 칸이 있을 때
around_check_and_action(nr, nc, new_sight, lst)
return
sight = new_sight # 다음 회전을 위해 방향 업데이트
# 네 방향 모두 청소된 경우 후진
back_dir = (sight + 2) % 4 # 현재 방향의 반대 방향
nr = row + dr[back_dir]
nc = col + dc[back_dir]
if 0 <= nr < N and 0 <= nc < M and lst[nr][nc] != 1: # 벽이 아닐 때
around_check_and_action(nr, nc, sight, lst)
# 로봇 청소 시작
around_check_and_action(r, c, sight, room)
# 최종 청소한 칸의 수 출력
print(cnt)
+ 항상 특정 위치에서 상,하,좌,우 탐색하는 문제만 풀었지, 이렇게 고개돌리는 문제를 처음 접해봐서 은근 까다로웠다...
역시 다양한 문제를 풀어봐야 하나보다.
Contents
소중한 공감 감사합니다