BrianaAI

문제.

https://www.acmicpc.net/problem/1182

풀이.

N, S = map(int, input().split())
data = list(map(int, input().split()))
tmp = [0] + [i for i in data]
answer = 0
def DFS(s, lst):
    global answer
    if sum(lst)==S and len(lst):
        answer+=1
    for i in range(s+1, N+1):
        DFS(i, lst+[tmp[i]])

DFS(0, [])
print(answer)

안녕하세요.

브리아나입니다.

오늘은 14503 백준 로봇청소기 문제를 풀어보겠습니다.

BFS(너비우선탐색, breadth-first-search)로 풀어보겠습니다.

문제링크.

https://www.acmicpc.net/problem/14503

문제 아이디어 정리하기.

1) 이슈가 될 수 있는 아이디어 정리하기

청소기 방향
cd = 0(북), 1(동), 2(남), 3(서) # cd: current direction
dx = [-1, 0, 1, 2]
dy = [0, 1, 0, -1]

청소기가 왼쪽 방향으로 회전한다.
현재 만약 서쪽이라면, 남->동->북->서 방향으로 회전
(현재 만약 3, 2->1->0->3 으로 회전)
IDEA: 보수를 더해주고 나머지 구하기 => (dr+3)%4
2-> 5%4 -> 1
1 -> 4%4 -> 0
0 -> 3%4 -> 3
3 -> 6%4 -> 2

2) 1번 항목부터 식을 세워보기.

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.

• 지도 = arr / 현재위치 (cx, cy) / 벽(1),청소x(0)이니까 청소하면(2)
• 청소 했는지 체크 count 변수

room_map[cx][cy] = 2
cnt+=1

2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
    바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
    바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.

• 후진: 방향 부호를 반전 시켜주면 됨.
  • bx = cx - dx[cd] (back_x = current_x - dx[current_direction]
  • if room_map[bx][by] != 1: # 벽 아니면 후진 가능
    • cx, cy = bx, by # 업데이트
    • 1번으로 돌아가야 하니까 순회(for) 멈추기: break
    • while문 빠져나갈 수 있게 (True -> False)

3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
    반시계 방향으로 90도 회전한다.
    바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
    1번으로 돌아간다.

• 왼쪽 방향부터 4방향 탐색 (다음 방향이니까 (nx, ny)) (이때, n은 next를 의미)
  • for: 빈곳(0) 있다? 2(청소) / 새로운 방향, 좌표 update
  • else: 빈곳(0) 없다? 후진 벽 아니라면? 후진 / 후진 벽이라면 종료

문제풀이.

1. 입력부, 출력부 작성하기

N, M = map(int, input().split())
cx, cy, cd = map(int, input().split())
room_map = [list(map(int, input().split())) for _ in range(N)]

def solution(cx, cy, cd):
	print("algorithm here")

print(solve(cx, cy, cd))

2. 전체 알고리즘 넣기

import sys
sys.stdin = open("input_14503.txt", "r")
# 북, 동, 남, 서 (반시계 90' 방향)
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

N, M = map(int, input().split())
cx, cy, cd = map(int, input().split()) # current_x, current_y, current_direction
room_map = [list(map(int, input().split())) for _ in range(N)]


def solution(cx, cy, cd):
    clean_count = 0

    while True:
        # 1) current room / no clean? / then, clean
        if room_map[cx][cy] == 0:
            room_map[cx][cy] = 2
            clean_count += 1
        con = True
        while con:
            for nd in ((cd+3)%4, (cd+2)%4, (cd+1)%4, cd): # condition access OK
                nx, ny = cx+dx[nd], cy+dy[nd]
                if room_map[nx][ny] == 0:
                    cx, cy, cd = nx, ny, nd
                    con = False
                    break # 청소 당첨되는 즉시 퇴장
            else: # no condition
                bx, by = cx-dx[cd], cy-dy[cd] # 후진
                if room_map[bx][by] != 1:
                    cx, cy = bx, by

                    break
                else:
                    return clean_count


print(solution(cx, cy, cd))

궁금한 사항 있으시면 질문 댓글로 주세요 :)