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)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

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

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
developer-ellen

인간 디버거의 로그 찍기

알고리즘/알고리즘문풀

BOJ - 벽 부수고 이동하기 2206번 (JAVA)

2022. 2. 7. 23:01

❓ 문제 - 백준 벽 부수고 이동하기 2206번 - JAVA 풀이법

 

출처 

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

 

2206번: 벽 부수고 이동하기

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로

www.acmicpc.net

 

 

 

📝 문제해결법

1. 이 문제는 BFS 알고리즘을 사용해서 풀었다.

  • N, M의 값이 1000으로 큰 값이기 때문에 시간을 고려해서 풀어야 한다. -> BFS
  • 벽은 한 번 부술 수 있으므로 벽을 부쉈을 때 방문체크 배열, 벽을 안 부쉈을 때 방문체크 배열을 따로 만들어야 한다.
  • 해당 위치에 벽을 부순 상태로 이미 방문했거나, 아직 벽을 부수지 않은 상태로 이미 방문 했지만 마지막에 벽에 막혀 방문하지 못 했을때, 다른 꼬불꼬불 길을 지나면서 해당 벽을 부수고 도착지에 올 수 있는 애가 이미 방문 처리 되었어서 그곳을 지날 수 없어 목적지에 도달 못한다고 판단할 수 있기 때문이다.
  • BFS 내에서는 4방향으로 탐색하면서, 아직 벽 부순 여부에 맞는 방문배열에 방문 처리가 되지 않았으면서, 이동할 곳이 지나갈 수 있으면 방문 처리 후 이동거리를 1 증가시킨 Node객체를 큐에 넣는다.
  • 그리고 이동할 곳이 벽이지만, 아직 벽을 부순 적이 없을 때 해당 벽을 부쉈을 때 방문처리 할곳에 방문처리하고, 벽을 부쉈다고 상태 변경하고 이동거리를 1 증가시킨 Node 객체를 큐에 넣는다.

2. 문제를 풀면서 느낀점

  • 파이썬으로 풀었는데, 자바로 다시 도전할 때 나름 만만하게 생각하다가 계속 메모리 초과 났다...
  • 나는 공간을 많이 잡아먹어서 메모리 초과가 나는 줄 알았는데 히든 테스트 케이스에서 방문처리 관련 잘못 구현하여 while문을 만약 빠져 나가지 못 했고 이게 메모리 초과가 났다..
  • 무한반복문에 빠져도 메모리초과와 같은 메시지를 받을 수 있다는 것을 명심하자...
  • 그리고 방문배열은 단순히 모든 경우의 수에서 방문 처리를 통해 계산하는 경우를 줄이기 위해 사용하므로, 이 문제에서 주어진 벽을 부순 상태에서 이동, 벽을 부수지 않은 상태에서 이동의 경우을 모두 살필 수 있게 방문 배열을 만들어야 하구나..!!!!!!!!!!!!!!!

 

💻 소스코드

import java.io.*;
import java.util.*;

public class Main_2206 {
    static int map[][];  // 통로 정보 입력 받을 배열
    static int visited[][][]; // visited[][][0] -> 아직 벽 부수지 않고 방문체크, visited[][][1] -> 벽 부순 후 방문 체크
    static int min_dis;
    public static class Node {
        int x;
        int y;
        int use;
        int dis;
        public Node(int x, int y, int use, int dis){
            this.x = x;
            this.y = y;
            this.use = use;
            this.dis = dis;

        }
    }
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int n, m;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);

        map = new int[n][m];
        visited = new int[n][m][2];
        // 지나가는 통로 정보 입력 받기
        for(int i=0;i<n;i++){
            String data = br.readLine();
            for(int j=0;j<m;j++){
                map[i][j] = data.charAt(j) -'0';
            }
        }
        min_dis = Integer.MAX_VALUE;
        // bfs 돌아서 움직이면서 map[n-1][m-1] 까지 가는 최소값 구하기
        bfs();
        // 만약 bfs 다 돌았는데 n-1, m-1 도달하지 못하면 min_dis 는 초기 주어진 값이므로 -1 출력하고
        // bfs 돌았는데 최소값 구하면 해당 값 출력
        if(min_dis == Integer.MAX_VALUE){
            System.out.println("-1");
        } else{
            System.out.println(min_dis);
        }



    }

    public static void bfs() {
        Queue<Node> q = new LinkedList<>();
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        // Node 객체에 행, 열 위치정보, 벽 부쉈는지 여부(0, 1), 이동 거리
        // 이동거리가 1인 이유는 문제에서 시작하는 칸과 끝나는 칸도 포함해서 이동거리를 센다고 조건 반영
        q.add(new Node(0, 0, 0, 1));
        // 0, 0은 아직 벽을 부수지 않은 상태(0)에서 방문처리
        visited[0][0][0] = 1;

        // queue가 빌 때까지 완전탐색
        while (!q.isEmpty()) {
            Node node = q.poll();
            // 만약 다 돌고 난 후 도착지이면 이때까지 이동할 때까지 걸린 거리를 최소 이동 거리랑 비교해서 최솟값 갱신
            if (node.x == n - 1 && node.y == m - 1) {
                min_dis = Math.min(min_dis, node.dis);
            }
            // 4방향 탐색
            for (int k = 0; k < 4; k++) {
                int nx = node.x + dx[k];
                int ny = node.y + dy[k];
                // 범위 벗어나지 않게 체크
                if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                    // 만약 방문했다면(이미 처리) 이곳은 탐색하지 않음
                  if(visited[nx][ny][node.use] != 0){
                      continue;
                  }

                  if (map[nx][ny] == 0){
                      // 이동할 곳이 이동할 수 있는 곳이면, 방문 처리 후 q에 이동거리 1증가시킨 node 객체 생성해서 큐에 추가
                      visited[nx][ny][node.use] = 1;
                      q.add(new Node(nx, ny, node.use, node.dis+1));
                  } else if(map[nx][ny] == 1 && node.use == 0){
                      // 만약 한번도 부순 적 없는 상태에서 벽을 만나면 한 번 벽을 부순 후 지나갈 수 있으므로
                      // 벽을 부순상태로 변경하고, 방문처리 후 큐에 추가
                      visited[nx][ny][1] = 1;
                      q.add(new Node(nx, ny, 1, node.dis+1));
                  }
                }

            }
        }
    }
}

 

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

BOJ - 상어 초등학교 21608번 (JAVA)  (0) 2022.02.11
BOJ - 효율적인 해킹 1325번 (JAVA)  (0) 2022.02.10
BOJ - 팰린드롬 만들기 1213번 (JAVA)  (0) 2022.02.02
BOJ - 기타줄 1049번 (JAVA)  (0) 2022.01.28
BOJ - A->B 16953번 (JAVA)  (0) 2022.01.25
    '알고리즘/알고리즘문풀' 카테고리의 다른 글
    • BOJ - 상어 초등학교 21608번 (JAVA)
    • BOJ - 효율적인 해킹 1325번 (JAVA)
    • BOJ - 팰린드롬 만들기 1213번 (JAVA)
    • BOJ - 기타줄 1049번 (JAVA)
    developer-ellen
    developer-ellen

    티스토리툴바