- 소요시간 : 20분 ( 벽 부수고 이동하기 2 의 코드를 그대로 사용. 그 코드에서 추가하는 작업 20분 )
- 문제 사이트 : 백준
- 문제 수준 : 골드 1
- 문제 유형 : 그래프 이론, 그래프 탐색, 너비 우선 탐색
- 다른 사람의 풀이를 참고 했는가 ? : X
- 한 번 풀었다가 다시 푸는 문제인가 ? : X
- 문제 링크 : https://www.acmicpc.net/problem/16933
- 푼 날짜 : 2023.03.24
1. 사용한 자료구조 & 알고리즘
BFS 를 사용했다.
2. 사고과정
먼저 기본적으로 벽 부수고 이동하기 2의 내용을 다 안다는 전제 하에 말하자면, 그 코드에서 추가해줘야 하는 부분은 지금이 낮인지, 밤인지이다. 그래서 Node class 에 afternoon이라는 field 를 추가해주었다.
기본적으로 다음 좌표가 빈칸일 때에는 이전의 코드와 같다. 하지만 이 때 추가로 낮과 밤을 반전시켜서 queue에 add 했다.
이제 여기서 내가 해준 시도는
(1) 만약 다음이 벽이고, 벽을 1개 더 부술 수 있고, 지금이 낮이라면
벽을 부수고, 방문처리하고, 밤이 되고, count를 1 증가시켜서 queue에 add
(2) 만약 다음이 벽이고, 벽을 1개 더 부술 수 있고, 지금이 밤이라면
벽을 부수고, 방문 처리하고, 밤낮을 바꾸지 않고, count를 2 증가시켜서 queue에 add
=>지금이 밤이면 다음 좌표까지 가는 데, count를 2 증가시키고 낮과 밤을 반전시키지 않은 상태로 갔다. 하지만 예제입력은 모두 통과했지만 오답처리.
반레가 뭘까 생각해봤는데 솔직히 답을 찾지 못했다.
그래서 2번째 시도를 했다. 그 시도는 통과를 했고, 풀이과정에 적도록 하겠다.
3. 풀이과정
1) 다음 좌표가 벽이고, 벽을 부술 수 있고, 아직 방문하지 않았고, 현재가 낮이라면 => 벽을 부수고, count를 1증가, 낮과 밤을 반전 시켜서 queue 에 add. 이후 방문 처리
2) 다음 좌표가 벽이고, 벽을 부술 수 있고, 밤이라면, 그냥 지금의 좌표를 한 번 더 count를 1증가, 낮과 밤을 반전시켜서 queue 에 add.
3) 2번의 경우에는이 때 아직 방문하지 않은 경우에만 방문하면 안된다. 왜냐하면 지금의 좌표를 올 때 이미 방문처리를 했기 때문에 그렇게 되면 다시 지금의 좌표에 1번 더 머무는 것에 대한 처리가 불가능 하다.
4. 소스코드
import java.io.*;
import java.util.*;
class Node{
int y;
int x;
int drill;
int count;
boolean afternoon;
Node(int y,int x,int drill,int count,boolean afternoon){
this.y=y;
this.x=x;
this.drill=drill;
this.count=count;
this.afternoon=afternoon;
}
}
public class Main {
static char map[][];
static int xx[]= {-1,1,0,0};
static int yy[]= {0,0,-1,1};
static StringBuilder sb=new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st=new StringTokenizer(br.readLine());
int n=Integer.parseInt(st.nextToken());
int m=Integer.parseInt(st.nextToken());
max=Integer.parseInt(st.nextToken());
map=new char[n][m];
for(int i=0;i<n;i++) {
String line=br.readLine();
for(int j=0;j<m;j++) {
map[i][j]=line.charAt(j);
}
}
bfs();
}
public static void bfs() {
boolean visited[][][]=new boolean[map.length][map[0].length][max+1];
visited[0][0][0]=true;
Queue<Node> queue=new LinkedList<>();
queue.add(new Node(0,0,0,1,true));
while(!queue.isEmpty()) {
Node temp=queue.poll();
int prevY=temp.y;
int prevX=temp.x;
int drill=temp.drill;
int count=temp.count;
boolean afternoon=temp.afternoon;
if(prevY==map.length-1&&prevX==map[0].length-1) {
System.out.println(count);
return;
}
for(int i=0;i<xx.length;i++) {
int nextY=prevY+yy[i];
int nextX=prevX+xx[i];
if(nextY<0||nextX<0||nextY>=map.length||nextX>=map[0].length) continue;
//낮과 밤이 반전된 형태
boolean reverse=!afternoon;
//빈칸이라면
if(map[nextY][nextX]=='0') {
//방문한 적이 없다면
if(visited[nextY][nextX][drill]==false) {
//count 를 1 증가시키고, 낮과 밤을 반전시켜서 queue에 add
queue.add(new Node(nextY,nextX,drill,count+1,reverse));
visited[nextY][nextX][drill]=true; //방문처리
}
}
//벽이라면
else {
//벽을 한 번 더 부술 수 있고 낮이라면
if(drill+1<=max&&afternoon) {
//방문하지 않았다면
if(visited[nextY][nextX][drill+1]==false) {
//벽을 부수고, count를 1 증가시키고 낮과 밤을 반전시켜서 queue에 add
queue.add(new Node(nextY,nextX,drill+1,count+1,reverse));
//방문처리
visited[nextY][nextX][drill+1]=true;
}
}
//벽을 한 번 더 부술 수 있고 밤이라면
else if(drill+1<=max&&!afternoon) {
// 그냥 현재 좌표를 다시 한 번 queue에 add. 낮과 밤은 반전, count 증가.
queue.add(new Node(prevY,prevX,drill,count+1,reverse));
}
}
}
}
System.out.println(-1);
}
}
5. 결과
제출 후 시간을 봤는데 2472 ms 로 꽤 많다고 생각해서 인터넷에 있는다른 분들의 코드로도 제출해 봤는데 3개 제출한 결과 내가 가장 빨랐다.
그중에서 하나는 아예 TLE가 났었다. ㅋㅋ 딱 시간대에 맞게 구성하셔서 어쩔 때는 되고 어쩔 때는 안되고 그러는 것 같다.
6. 회고
두 번째로 푼 골드 1 문제.
조만간 플레 입문 문제인 히스토그램에서 가장 큰 직사각형 문제에도 도전해 볼 수 있지 않을까?
하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212
