ddingurri
유원준의 개발로그
ddingurri
전체 방문자
오늘
어제
  • 전체글 (37)
    • PS (7)
      • BOJ (5)
      • Programmers (0)
      • 후기 (2)
    • CS (22)
      • Data Structure (0)
      • Java (6)
      • OOP (2)
      • Spring (7)
      • WEB (3)
      • Database (4)
    • Develop (2)
    • Books (2)
    • Daily (4)
      • moments (0)
      • 회고 (4)

블로그 메뉴

    공지사항

    인기 글

    태그

    • 23288 파이썬
    • 백준
    • 객체지향의 사실과 오해 후기
    • 책 스터디
    • 객체지향의 사실과 오해
    • 삼성 문제집 파이썬
    • mysql 소수점
    • float 소수점
    • 객체지향의 사실과 오해 1장
    • 상어 초등학교
    • 백준 주사위 굴리기2
    • Java
    • mysql float
    • Spring
    • 객사오 2장
    • MySQL
    • 주사위 굴리기2 파이썬
    • 상어 중학교 python3
    • 객체지향의 사실과 오해 리뷰
    • 객체지향의 사실과 오해 2장
    • 상어 중학교
    • 스프링
    • 주사위굴리기2
    • 객체지향의 사실과 오해 요약
    • SWEA
    • 주사위 굴리기2
    • 백준 주사위 굴리기2 파이썬
    • 상어 중학교 python
    • 21609 파이썬
    • 주사위굴리기2 파이썬

    최근 댓글

    최근 글

    티스토리

    hELLO · Designed By 정상우.
    ddingurri

    유원준의 개발로그

    PS/BOJ

    [백준] 14503. 로봇 청소기 (파이썬)

    2022. 2. 19. 12:39

    문제

    로봇 청소기

    로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

     

    시간 제한 2초

    메모리 제한 512MB

     

    • 공간의 크기 N x M
    • 로봇 청소기는 바라보는 방향이 있다.
      • 0 : 북, 1 : 동, 2 : 남, 3 : 서
    • 각 칸의 상태는 숫자로 표시됨
      • 0 : 빈칸,  1 : 벽(이동 불가)
    •  로봇 청소기의 작동 방식
    1. 현재 위치를 청소한다.
    2. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다.     

          a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.

          b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.

          c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.

          d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

     

       로봇 청소기는 이미 청소되어 있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.


    풀이

    완전탐색 알고리즘들(브루트포스, bfs, dfs 등)중, 

    주어진 공간 전부를 탐색하지 않고, 로봇청소기가 조건에 맞게 이동할 수 있는 경로만을 탐색하므로

    DFS(재귀) 스타일이 가장 적합하다고 생각했다.

     

     

    이 문제에서의 핵심 구현 포인트는 두 가지이다.

    1. 방향 회전을 어떻게 할까?

    # 0: 북, 1: 동, 2: 남, 3: 서
    # dx = [-1, 0, 1, 0]	
    # dy = [0, 1, 0, -1]
    # 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다.
    	new_d = d
    	for _ in range(4):
    		#왼쪽 방향부터 탐색
    		new_d = (new_d + 3) % 4
    		nx = x + dx[new_d]
    		ny = y + dy[new_d]

    로봇청소기의 방향 정보(d)가 int 입력값이므로

    해당 값을 방향벡터의 index로 활용할 수 있도록 dx, dy 리스트를 저장하였다.

     

    방향을 왼쪽으로 회전하는 방법은

    new_d 값에서 -1을 더해주거나, 3을 더해주는 방법이 있다.

     

    하지만 0에서 -1을 하게 될 경우, 별도의 값 처리가 필요하므로 

    3을 더해주는 방식을 채택하였다.

     

    2. 후진을 어떻게 할까?

    #c. 네 방향 모두 청소가 되어 있는 경우: 바라보는 방향을 유지한 채로 한칸 후진.
    	bx = x - dx[d]
    	by = y - dy[d]
    	
    	if board[bx][by] != 1:
    		dfs(bx, by, d)
    	#d. 이때, 후진 불가능한 경우: 탐색 종료
    	return

    위와 같은 방식으로 후진을 위해

     

    (new_d + 2) % 4 를 계산하여 이용하는 방법도 있었지만,

    위와 같은 방법으로 기존 좌표에서 값을 빼 주면 

    d값을 유지하면서 반대 방향으로 이동이 가능하다.

     

    코드

    import sys
    
    input = sys.stdin.readline
    
    '''
    풀이 방법: DFS
    시간 복잡도 : O(n^4) 
    공간 복잡도 : O(n^2)
    '''
    
    def dfs(x, y, d):
    	global res
        #1. 현재 위치를 청소한다. 
        #청소 시, 청소하지 않은 칸과 구분을 위해 값을 2로 갱신해주었다.
    	if not board[x][y]:
    		board[x][y] = 2
    		res += 1
        
        #2. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다.
    	new_d = d
    	for _ in range(4):
    		#왼쪽 방향부터 탐색
    		new_d = (new_d + 3) % 4
    		nx = x + dx[new_d]
    		ny = y + dy[new_d]
    
    		#청소 가능한 칸을 발견하면
    		if not board[nx][ny]:
    			dfs(nx, ny, new_d)
    			return
        
        #c. 네 방향 모두 청소가 되어 있는 경우: 바라보는 방향을 유지한 채로 한칸 후진.
    	bx = x - dx[d]
    	by = y - dy[d]
    	
    	if board[bx][by] != 1:
    		dfs(bx, by, d)
    	#d. 이때, 후진 불가능한 경우: 탐색 종료
    	return
    
        
    if __name__ == "__main__":
    	n, m = map(int, input().rstrip('\n').split())
    	r, c, d = map(int, input().rstrip('\n').split())
    	board = []
    
    	for i in range(n):
    		board.append(list(map(int, input().rstrip('\n').split())))
    		
        #d값에 맞게 방향벡터 설정
    	dx = [-1, 0, 1, 0]
    	dy = [0, 1, 0, -1]
    
    	res = 0 
        #로봇 청소기 작동
    	dfs(r, c, d)
    
    	print(res)

     

    삼성 기출 문제들 중 구현, 시뮬레이션 문제들은 문제 길이가 정말 긴 편이다.

    문제를 꼼꼼하게 읽고, 요구사항에 맞게 차근차근 구현하면 된다.

    저작자표시 (새창열림)

    'PS > BOJ' 카테고리의 다른 글

    [백준] 23288. 🎲주사위 굴리기 2 (파이썬)  (0) 2023.08.04
    [백준] 21609. 상어 중학교 (파이썬)  (0) 2022.03.20
    [백준] 16236. 아기 상어 (파이썬)  (0) 2022.02.28
    [백준] 17142. 연구소 3 (파이썬)  (1) 2022.02.28
      'PS/BOJ' 카테고리의 다른 글
      • [백준] 23288. 🎲주사위 굴리기 2 (파이썬)
      • [백준] 21609. 상어 중학교 (파이썬)
      • [백준] 16236. 아기 상어 (파이썬)
      • [백준] 17142. 연구소 3 (파이썬)
      ddingurri
      ddingurri

      티스토리툴바