[BAEKJOON] 14503번 : 로봇청소기 (JAVA)

2022. 2. 21. 21:00· Algorithm
반응형

- 알고리즘 분류 : DFS

- 사용 언어 : JAVA

- 문제 요점

  1. 청소기가 방을 돌아다니며 청소한 방의 수를 구하는 문제
  2. 로봇청소기의 작동하는 방식을 그대로 구현하면 어렵지 않은 문제
  3. DFS를 이용하여 풀이

 

소스 설명은 주석을 참고해주세요.

 

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

public class Main {

	// N x M 크기의 맵
	// r,c : 현재 청소기의 위치. d : 청소기의 방향
	public static int N, M, r, c, d;
	
	// 맵
	public static int[][] map;
	
	// 순서대로 북, 동, 남, 서
	public static int[] amove = {-1,0,1,0};
	public static int[] bmove = {0,1,0,-1};
	
	// 결과
	public static int result = 0;
	
	// DFS탐색
	public static void DFS(int r, int c, int d, int cnt) {
		// 0 : 빈 방
		// 1 : 벽
		// 2 : 청소완료한 방 
		
		// 청소체크
		map[r][c] = 2;
		
		// 결과값 갱신
		result = Math.max(result, cnt);
		
		int temp = d;
		
		// 네 방향의 방이 모두 청소가 되어있는 지 체크
		boolean check = false;
		
		// 상하좌우체크
		for(int i=0; i<4; i++) {
			// 좌측부터 체크(현재 바라보고 있는 방향 기준 왼쪽부터 탐색)
			temp = (temp+3)%4;
			
			int tempA = r+amove[temp];
			int tempB = c+bmove[temp];
			
			// 범위 이내이고, 빈 방이라면 DFS 탐색진행
			if(tempA > 0 && tempA < N && tempB > 0 && tempB < M) {
				if(map[tempA][tempB] == 0) {
					DFS(tempA, tempB, temp, cnt+1);
					check = true;
					break;
				}
			}
		}
		
		// 위에서 빈 방을 찾지 못한 경우
		if(check == false) {
			// 바라보고 있는 방향의 뒤로 이동
			int reverse = (d+2)%4;
			
			int reverseA = r+amove[reverse];
			int reverseB = c+bmove[reverse];
			
			// 범위 이내이고 벽이 아니라면 뒤로 이동(Cnt 증가 X)
			if(reverseA > 0 && reverseA < N && reverseB > 0 && reverseB < M) {
				if(map[reverseA][reverseB] != 1) {
					DFS(reverseA, reverseB, d, cnt);
				}
			}
		}
	}
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new int[N][M];
		
		st = new StringTokenizer(br.readLine());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		d = Integer.parseInt(st.nextToken());
		
		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()); 
			}
		}
		
		// DFS탐색
		DFS(r,c,d,1);
		
		// 청소한 방의 수 출력
		System.out.println(result);
	}

}
반응형

'Algorithm' 카테고리의 다른 글

[BAEKJOON] 2573번 : 빙산 (JAVA)  (0) 2022.02.22
[BAEKJOON] 9205번 : 맥주 마시면서 걸어가기 (JAVA)  (0) 2022.02.21
[BAEKJOON] 5014번 : 스타트링크 (JAVA)  (0) 2022.02.20
[BAEKJOON] 2468번 : 안전영역 (JAVA)  (0) 2022.02.20
[BAEKJOON] 1929번 : 소수구하기 (JAVA)  (0) 2022.02.18
'Algorithm' 카테고리의 다른 글
  • [BAEKJOON] 2573번 : 빙산 (JAVA)
  • [BAEKJOON] 9205번 : 맥주 마시면서 걸어가기 (JAVA)
  • [BAEKJOON] 5014번 : 스타트링크 (JAVA)
  • [BAEKJOON] 2468번 : 안전영역 (JAVA)
멍목
멍목
개발 관련 새롭게 알게 된 지식이나 좋은 정보들을 메모하는 공간입니다.
반응형
멍목
김멍목의 개발블로그
멍목
전체
오늘
어제
  • 분류 전체보기 (514)
    • BE (190)
      • Spring (21)
      • Java (141)
      • Kotlin (6)
      • JPA (22)
    • FE (33)
      • Javascript (16)
      • Typescript (0)
      • React (5)
      • Vue.js (9)
      • JSP & JSTL (3)
    • DB (32)
      • Oracle (22)
      • MongoDB (10)
    • Algorithm (195)
    • Linux (8)
    • Git (6)
    • etc (42)
    • ---------------------------.. (0)
    • 회계 (4)
      • 전산회계 2급 (4)
    • 잡동사니 (2)

블로그 메뉴

  • 홈
  • 관리

공지사항

인기 글

태그

  • MongoDB 기초부터 실무까지
  • MongoDB 공부
  • vue3 공부
  • MongoDB with Node.js
  • 자바 개발자를 위한 코틀린 입문
  • 알고리즘 공부
  • JPA
  • 이펙티브 자바
  • JPA 공부
  • 알고리즘공부
  • 코테 공부
  • 자기 공부
  • 더 자바 Java 8
  • 자바공부
  • 코테공부
  • 자기 개발
  • java 8
  • Java to Kotlin
  • Effective Java
  • junit5
  • 코틀린
  • 자기개발
  • 더 자바 애플리케이션을 테스트하는 다양한 방법
  • 자기공부
  • 전산회계 2급 준비
  • Oracle
  • 프로젝트로 배우는 Vue.js 3
  • 자바 테스팅 프레임워크
  • 이펙티브자바
  • 자바 공부

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.0
멍목
[BAEKJOON] 14503번 : 로봇청소기 (JAVA)
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.