https://www.acmicpc.net/problem/3055
3055번: 탈출
사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제
www.acmicpc.net
코드설명
BFS 문제입니다.
문제에서 유의해야할점들입니다.
1. 물이 여러개 주어질 수 있습니다. (처음에 물이 무조건 1개만 주어지는줄알고 코딩했습니다.)
2. Queue의 얕은복사와 깊은복사.
처음에 아래와 같이 진행하며 Queue가 자동으로 깊은복사가 되는 줄 알았지만 얕은복사가 되어 주소값을 참조하게 됩니다. 그럴경우에 둘이 같은 주소값을 가리키게 되면서 당연히 작동하지 않습니다. waterQ = newWaterQ.; 얕은복사로 이후에 pop되면서 사라집니다.. gosumdochiQ = newGosumdochiQ; 그대신 아래와 같이 진행합니다. while(!newWaterQ.isEmpty()) { waterQ.add(newWaterQ.poll()); } while(!newGosumdochiQ.isEmpty()) { gosumdochiQ.add(newGosumdochiQ.poll()); } // 처음에 아예 생각을 잘못하고 for(Node a : newGosumdochiQ) { gosumdochiQ.add(a); } Queue를 단순 순회하여 실수했었습니다.
3. 현재 따로 newQueue를 선언하여 진행하지만, int currentLength = q.size() 를 통해서 굳이 새로운 newQueue를 선언하지 않고 진행하는 방법도 있습니다.
메모리사용면에서 위의 size 방식을 사용하는것이 나을것 같습니다.
4. '*'는 여러개일 수 있습니다. 혹은 없을 수도 있습니다.
public static Node gosumdochiNode = null, waterNode = null; 를 선언하여 q.add(waterNode)를 진행했었는데 이럴경우에 물이 없는경우 null값이 들어가지만 q.size()는 똑같이 1 입니다. 이유는 waterNode가 null 안상태로 들어갔기에 Queue를 활용하면 nullPoitnerException이 나오기에 아래와 같이 만날떄마다 넣는것으로 수정하였습니다. 이러한 오류가 발생한 이유는 'S'와 '*'가 무조건 1개일것이라고 생각하여서 발생한 문제입니다. 문제를 잘읽고 풀어야합니다. for(int i=0;i<N;i++) { for(int j=0;j<M;j++) { if(map[i][j] == 'S') { //고슫도치의 위치 gosumdochiQ.add(new Node(i,j)); } else if(map[i][j] == '*') { //물의 위치 waterQ.add(new Node(i,j)); } } }
10 11 D.......... ........... ........... ........... ........... ........... ........S.. ........... ........... ........... 14 테스트케이스 도움받은글 https://www.acmicpc.net/board/view/27210
코드
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { public static int N, M; public static char[][] map; public static int[] dx= {-1,1,0,0}; public static int[] dy = {0,0,-1,1}; public static int answer=0; // public static Node gosumdochiNode = null, waterNode = null; public static Queue<Node> waterQ = new LinkedList<Node>(); public static Queue<Node> gosumdochiQ = new LinkedList<Node>(); 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()); map = new char[N][M]; for(int i=0;i<N;i++) { st = new StringTokenizer(br.readLine()); map[i] = st.nextToken().toCharArray(); } for(int i=0;i<N;i++) { for(int j=0;j<M;j++) { if(map[i][j] == 'S') { //고슫도치의 위치 gosumdochiQ.add(new Node(i,j)); } else if(map[i][j] == '*') { //물의 위치 waterQ.add(new Node(i,j)); } } } simulate(); if(answer == 0) { System.out.println("KAKTUS"); }else { System.out.println(answer); } } public static void simulate() { Queue<Node> newWaterQ = new LinkedList<Node>(); Queue<Node> newGosumdochiQ = new LinkedList<Node>(); int time =0 ; while(true) { time += 1; if(gosumdochiQ.isEmpty()) { return ; //만약 더이상 고슴도치에 큐가 없다면 고슴도치가 없는것이므로 실패임. } while(!waterQ.isEmpty()) { Node temp = waterQ.poll(); int r = temp.r; int c = temp.c; for(int dir=0;dir<4;dir++) { int nr = r + dx[dir]; int nc = c + dy[dir]; if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue; if(map[nr][nc] != '.') continue; map[nr][nc] = '*'; newWaterQ.add(new Node(nr, nc)); } } while(!gosumdochiQ.isEmpty()) { Node temp = gosumdochiQ.poll(); int r = temp.r; int c = temp.c; for(int dir=0;dir<4;dir++) { int nr = r + dx[dir]; int nc = c + dy[dir]; if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue; if(map[nr][nc] == 'S') continue; if(map[nr][nc] == 'X' || map[nr][nc] =='*') continue; //물은 '벽'과 '굴'로 이동할 수 없음 if(map[nr][nc] == 'D') { answer = time; return ; } map[nr][nc] = 'S'; newGosumdochiQ.add(new Node(nr, nc)); } } while(!newWaterQ.isEmpty()) { waterQ.add(newWaterQ.poll()); } while(!newGosumdochiQ.isEmpty()) { gosumdochiQ.add(newGosumdochiQ.poll()); } } } } class Node{ int r; int c; public Node(int r, int c) { this.r=r; this.c=c; } }
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 10026 적록색약 - BFS JAVA (0) | 2023.09.12 |
---|---|
[백준] 1963 소수 경로 - BFS + 에라토스테네스의 체 + 소수 판정 JAVA (0) | 2023.09.12 |
[백준] 16946 벽 부수고 이동하기 4 - BFS + 방문처리 + 시간초과 JAVA (0) | 2023.09.11 |
[백준] 16993 벽 부수고 이동하기 3 - BFS + 방문처리 JAVA (0) | 2023.09.11 |
[백준] 14442 벽 부수고 이동하기 2 - BFS + 방문처리 JAVA (0) | 2023.09.11 |