developer-ellen
인간 디버거의 로그 찍기
developer-ellen
전체 방문자
오늘
어제
  • 분류 전체보기 (217)
    • 회고록 (0)
    • 취뽀 및 커리어 여정의 Stack (2)
      • SSAFY 7기 (2)
    • 프로그래밍공부 (24)
      • c++ (0)
      • JAVA (3)
      • Spring (5)
      • design pattern (3)
      • BackDB (1)
      • Servlet&JSP (3)
      • Vue (4)
      • JPA (4)
      • Infra (1)
      • Linux (0)
    • AI (3)
      • papers (3)
      • trend (0)
    • 프로젝트진행 (0)
      • 데이터베이스 (0)
      • 서버개발 (0)
      • 인공지능 (0)
      • 하루정리 (0)
    • 포트폴리오 (0)
    • 알고리즘 (158)
      • 알고리즘문풀 (155)
      • 알고리즘공부 (3)
    • 통계공부 (15)
      • 시계열분석 (15)
      • 회귀분석 (0)
    • CS (14)
      • 컴퓨터네트워크 (4)
      • 운영체제 (8)
      • 데이터베이스 (2)
    • 주저리주저리 (0)
      • 필사 (0)
    • 취업관련정보 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 삼성코테파이썬
  • 시계열분석
  • 삼성코테구현풀이
  • 통계학
  • 삼성코테기출
  • c++ 빌더 패턴
  • SW역량테스트파이썬풀이
  • c++디자인패턴
  • 백준파이썬풀이
  • 삼성코테구현문제추천
  • 운영체제인터럽트
  • 통계분석
  • 삼성코테기출자바풀이
  • 삼성코테자바준비
  • Arima
  • 시계열
  • 삼성코테준비
  • MA모형
  • AR모형
  • 카카오코테java풀이
  • 데이터분석
  • ARIMA모형
  • 삼성코테파이썬풀이
  • 삼성코테자바꿀팁
  • 삼성코테자바풀이
  • BOJ파이썬풀이
  • 삼성코테파이썬준비
  • 카카오코테
  • 코테파이썬
  • SW역량테스트파이썬

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
developer-ellen

인간 디버거의 로그 찍기

알고리즘/알고리즘문풀

BOJ - 로봇 청소기 14503번 (JAVA)

2022. 4. 17. 01:22

❓ 문제 - 백준 로봇 청소기 14503번 - JAVA 풀이법

출처 

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

 

14503번: 로봇 청소기

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어

www.acmicpc.net

 

 

📝 문제해결법

1. 이 문제는 구현으로 풀었다.

  • 주어진 문제 흐름 그대로 구현했다.
  • while 두 개를 활용하였다
  • 처음 outer1 while문은 전체 로봇 청소기의 운행으로 보면 된다. 따라서 현재 위치를 청소 하고 outer2에서 청소할 영역을 탐색한다.
  • 현재 방향에서 왼쪽에 있는 곳에 청소를 아직 안 한 빈칸이라면 영역을 찾았으니깐 outer2의 while문을 빠져나간다.
  • 만약 청소를 아직 안한 빈칸이 아니거나 벽이라면 로봇 청소기의 방향을 왼쪽방향으로 돌려 다시 왼쪽 부분을 체크한다.
  • 4방향 모두 왼쪽에 있는 영역을 체크 했는데 청소할 영역을 찾지 못한다면 후진을 시작한다.
  • 만약 후진할 곳이 벽이거나 범위를 넘는 값이라면 로봇 청소기의 운행을 종료하기 위해 outer1의 while문을 빠져나간다.
  • 계속 while문을 돌면서 로봇 청소기의 운행을 하고 청소한 영역을 cnt으로 카운트 해준 후 마지막에 로봇 청소기가 종료하면 cnt 값을 출력한다.

2. 방향 전환

  • dx, dy를 북 - 동  - 남 - 서로 구현하고, 현재 방향을 dir 변수를 통해 인덱스 값을 저장한다. 만약 현재 방향에서 왼쪽 방향이나 왼쪽인 곳을 탐색할 때는 북 ->서, 서 -> 남, 남 -> 동, 동 -> 북 이므로 dir=(dir+3) % 4로 인덱스의 변화를 주면 맞춰서 방향을 변화시킬 수 있다.
  • 후진의 경우도 위의 마찬가지로 북 -> 남, 동 -> 서, 남 -> 북, 서 -> 북으로 처리해야하기 때문에 dir=(dir+2)%4로 인덱스의 변화를 준다.

3. 느낀점

  • 문제에 맞춰서 잘만 구현해주면 되기 때문에 큰 어려움은 없었다.
  • 다른 사람들의 풀이를 참고 할 때 나처럼 while문을 여러개 사용한 것이 아니라 재귀를 통해 계속 로봇 청소기의 이동 시켜 청소하도록 구현하였다. 좀 더 코드를 간결하고 좋게 구현하려면 이 방법이 훨씬 좋은 것 같다. 오늘도 배웠다 !! ㅎㅎ

 

💻 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_14503 {
	public static int n, m;
	public static int[][] map;
	public static int x, y, dir;
	// 북 , 동, 남, 서
	public static int[] dx = {-1, 0, 1, 0};
	public static int[] dy = {0, 1, 0, -1};
	public static boolean[][] visited;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine(), " ");
		x = Integer.parseInt(st.nextToken());
		y = Integer.parseInt(st.nextToken());
		dir = Integer.parseInt(st.nextToken());
		map = new int[n][m];
		visited = new boolean[n][m];
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0;j<m;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int cnt = 0;
		outer1:while(true) {
			// 현재 칸 청소
			visited[x][y] = true;
			cnt++;

			
			

			// 인접한 칸 탐색
			outer2:while(true) {
            	boolean check = false;
				for(int i=0;i<4;i++) {
					int d = (dir+3)%4;
					int	nx = x + dx[d];
					int ny = y + dy[d];
					if(0 <= nx && nx < n && 0 <= ny && ny < m) {
						if(!visited[nx][ny] && map[nx][ny] != 1) {
							dir = (dir==0?3:dir-1);
							x = nx;
							y = ny;
							check = true;
							break outer2;
						}
					}
					// 왼쪽에 빈공간이나 청소할 공간 존재하지 않다면 왼쪽방향으로 회전
					dir = (dir+3) % 4;
				}
				
				
				// 네 번 방향 청소할 곳 못 찾았을 때
				if(!check) {
					int d = (dir+2)%4;
					int nx = x + dx[d];
					int ny = y + dy[d];
					if(nx < 0 || nx >=n || ny < 0 || ny >= m || map[nx][ny] == 1) {
						break outer1;
					}
					// 후진
					x = nx;
					y = ny;
				}
				
			}
			
			
			
		}
		

		System.out.println(cnt);
	

		
		
	}
}

'알고리즘 > 알고리즘문풀' 카테고리의 다른 글

BOJ - 사다리 조작 15684번 (JAVA)  (0) 2022.04.21
BOJ - 감시 15683번 (Java)  (0) 2022.04.21
BOJ - 테트로미노 14500번 (JAVA)  (0) 2022.04.12
BOJ - 주사위 굴리기 14499번 (JAVA)  (0) 2022.04.11
BOJ - 시험 감독 13485번 (JAVA)  (0) 2022.04.08
    '알고리즘/알고리즘문풀' 카테고리의 다른 글
    • BOJ - 사다리 조작 15684번 (JAVA)
    • BOJ - 감시 15683번 (Java)
    • BOJ - 테트로미노 14500번 (JAVA)
    • BOJ - 주사위 굴리기 14499번 (JAVA)
    developer-ellen
    developer-ellen

    티스토리툴바