목차
728x90
벽 부수고 이동하기
https://www.acmicpc.net/problem/2206
2206번: 벽 부수고 이동하기
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로
www.acmicpc.net
풀이
import annotation.boj.BOJ;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.stream.Collectors;
@BOJ
public class 백준2206 {
public static void main(String[] args) throws IOException, IOException {
/**
* 입력을 받아서 Row와 Column 사이즈를 지정한다.
*/
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] inputs = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int COL_SIZE = inputs[1];
int ROW_SIZE = inputs[0];
/**
* Map 정보를 입력받는다
*/
ArrayList<ArrayList<Integer>> map = new ArrayList<>(new ArrayList<>());
for(int i =0; i< ROW_SIZE; i++){
map.add(new ArrayList(Arrays.stream(br.readLine().split(""))
.map((String s) ->{
if(s.equals("1")) return null;//벽이면 null을
return 0;}) //아니면 0을 입력한다.
.collect(Collectors.toList())));
}
/**
* map을 방문했는지 체크한 결과를 가진 배열을 생성한다.
*/
boolean[][][] visited = new boolean[ROW_SIZE][COL_SIZE][2];
int[] dy = {0,0,-1,1};
int[] dx = {-1,1,0,0};
/**
* BFS를 수행할 Deque를 생성한 뒤 첫번째 값을 넣는다.
*/
Deque<Location> deque = new ArrayDeque<>();
deque.offer(Location.of(1,0,0,false));//count, x, y ,벽을 부순 적 있는지 여부
visited[0][0][0]=false;
while (!deque.isEmpty()){
Location current = deque.poll();
int X = current.getX();
int Y = current.getY();
if(X == COL_SIZE-1 && Y == ROW_SIZE-1){//마지막이라면 출력한다.
System.out.println(current.getCount());
return;
}
boolean destroyWall = current.isDestroyWall();//현재 벽을 부순 상태인지를 저장
int destroyed = destroyWall ? 1 : 0;//벽을 부섰다면 1, 아니라면 0
for(int i=0; i<4; i++){
int nx = X + dx[i];
int ny = Y + dy[i];
if(nx < 0 || ny < 0 || nx >= COL_SIZE || ny >= ROW_SIZE) continue;
if(map.get(ny).get(nx) != null) {//벽이 아니면
if ( visited[ny][nx][destroyed]) continue;
deque.offer(Location.of(current.getCount() + 1, nx, ny, destroyWall));
visited[ny][nx][destroyed] = true;
}else{
if (!destroyWall){
deque.offer(Location.of(current.getCount() + 1, nx, ny, true));
visited[ny][nx][1] = true;
}
}
}
}
System.out.println("-1");
}
private static class Location {
private int count;
private int x;
private int y;
private boolean isDestroyWall;
private Location(int count, int x, int y, boolean isDestroyWall) {
this.count = count;
this.x = x;
this.y = y;
this.isDestroyWall = isDestroyWall;
}
public static Location of(int count, int x, int y, boolean isDestroyWall){
return new Location(count,x,y,isDestroyWall);
}
public int getCount() {
return count;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
public boolean isDestroyWall() {
return isDestroyWall;
}
}
}
728x90
'Algorithm > 백준' 카테고리의 다른 글
[백준/10816/Java] 숫자 카드 2 (0) | 2022.02.13 |
---|---|
[백준/1920/Java] 수 찾기 (0) | 2022.02.12 |
[백준/7562/Java] 나이트의 이동 (0) | 2022.02.10 |
[백준/1697/Java] 숨바꼭질 (0) | 2022.02.09 |
[백준/7569/Java] 토마토 (0) | 2022.02.09 |
728x90
벽 부수고 이동하기
https://www.acmicpc.net/problem/2206
2206번: 벽 부수고 이동하기
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로
www.acmicpc.net
풀이
import annotation.boj.BOJ;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.stream.Collectors;
@BOJ
public class 백준2206 {
public static void main(String[] args) throws IOException, IOException {
/**
* 입력을 받아서 Row와 Column 사이즈를 지정한다.
*/
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] inputs = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int COL_SIZE = inputs[1];
int ROW_SIZE = inputs[0];
/**
* Map 정보를 입력받는다
*/
ArrayList<ArrayList<Integer>> map = new ArrayList<>(new ArrayList<>());
for(int i =0; i< ROW_SIZE; i++){
map.add(new ArrayList(Arrays.stream(br.readLine().split(""))
.map((String s) ->{
if(s.equals("1")) return null;//벽이면 null을
return 0;}) //아니면 0을 입력한다.
.collect(Collectors.toList())));
}
/**
* map을 방문했는지 체크한 결과를 가진 배열을 생성한다.
*/
boolean[][][] visited = new boolean[ROW_SIZE][COL_SIZE][2];
int[] dy = {0,0,-1,1};
int[] dx = {-1,1,0,0};
/**
* BFS를 수행할 Deque를 생성한 뒤 첫번째 값을 넣는다.
*/
Deque<Location> deque = new ArrayDeque<>();
deque.offer(Location.of(1,0,0,false));//count, x, y ,벽을 부순 적 있는지 여부
visited[0][0][0]=false;
while (!deque.isEmpty()){
Location current = deque.poll();
int X = current.getX();
int Y = current.getY();
if(X == COL_SIZE-1 && Y == ROW_SIZE-1){//마지막이라면 출력한다.
System.out.println(current.getCount());
return;
}
boolean destroyWall = current.isDestroyWall();//현재 벽을 부순 상태인지를 저장
int destroyed = destroyWall ? 1 : 0;//벽을 부섰다면 1, 아니라면 0
for(int i=0; i<4; i++){
int nx = X + dx[i];
int ny = Y + dy[i];
if(nx < 0 || ny < 0 || nx >= COL_SIZE || ny >= ROW_SIZE) continue;
if(map.get(ny).get(nx) != null) {//벽이 아니면
if ( visited[ny][nx][destroyed]) continue;
deque.offer(Location.of(current.getCount() + 1, nx, ny, destroyWall));
visited[ny][nx][destroyed] = true;
}else{
if (!destroyWall){
deque.offer(Location.of(current.getCount() + 1, nx, ny, true));
visited[ny][nx][1] = true;
}
}
}
}
System.out.println("-1");
}
private static class Location {
private int count;
private int x;
private int y;
private boolean isDestroyWall;
private Location(int count, int x, int y, boolean isDestroyWall) {
this.count = count;
this.x = x;
this.y = y;
this.isDestroyWall = isDestroyWall;
}
public static Location of(int count, int x, int y, boolean isDestroyWall){
return new Location(count,x,y,isDestroyWall);
}
public int getCount() {
return count;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
public boolean isDestroyWall() {
return isDestroyWall;
}
}
}
728x90
'Algorithm > 백준' 카테고리의 다른 글
[백준/10816/Java] 숫자 카드 2 (0) | 2022.02.13 |
---|---|
[백준/1920/Java] 수 찾기 (0) | 2022.02.12 |
[백준/7562/Java] 나이트의 이동 (0) | 2022.02.10 |
[백준/1697/Java] 숨바꼭질 (0) | 2022.02.09 |
[백준/7569/Java] 토마토 (0) | 2022.02.09 |