BOJ/2206_벽 부수고 이동하기

[문제]

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

[처음 생각]

https://www.acmicpc.net/problem/2178 

보자마자 이 문제인줄 알았다. 대신 이 문제에서 벽을 한번 부술 수 있다는 기회가 있다는 점이 차이점이었다. 

벽을 한번 부술 수 있는 대신에 가장 최단으로 갈 수 있는 거리를 찾아야 한다. 내가 소스를 짜봤을 때는 탐색하는 다음 방향의 블럭이 0일 때와 1일 때로 나눠서 생각했다. 그리고 그 안에서 전의 블럭(바로 큐에서 꺼낸 블럭)이 벽을 뚫고 온 상태인지 아닌지를 체크하며 벽을 뚫는 횟수 변수인 wall을 사용할 예정이었다. 

[풀이]

결국 소스를 참고 했는데...

내가 생각한 것처럼 다음 방향의 블럭이 0일 때와 1일 때로 나눠서 하는건 맞았다. 대신 visited배열을 2차원이 아닌, 3차원 배열로 만들어서 벽을 뚫고 왔는지(1) 아닌지(0)를 같이 체크할 수 있도록 했다. 그리고 3차원 배열을 Integer.MAX_VALUE로 초기화해서 나중에 방문을 체크하도록 했다. 

[다른 풀이]

Data라는 클래스에 변수로 x, y, 지나치는 블럭을 세는 depth, 벽을 뚫는 스킬을 썼는지 여부의 skill(1이면 쓴것)을 만듦

result 전역변수 선언

visited[][][skill여부] 선언

<main 함수>

//어짜피 여기서 인덱스 1부터 n과 m까지 사용할거라서 인덱스 0부터인지 1부터인지 중요 ㄴㄴ

기본 map을 -1로 초기화

visited는 0으로 초기화

map을 인덱스 1부터 n과 m까지 입력받음

//1,1을 시작으로 시작칸 포함해서 1의 depth와 skill 안씀

BFS(1, 1, 1, 0) 호출

result가 0이면 -1 출력

아니면 result 출력

<BFS 함수>

//매개변수(x, y, depth, skill)

큐에 Data 객체로 매개변수로 들어온것들 넣음

while(!qu.isEmpty())

{

Data temp = qu.remove();

//map 범위 체크

//map 벗어나는지 체크(-1인지)

//이미 방문했는지 체크

////아니라면 방문처리

//만약 현재 좌표가 목표지점인 (n,m)이면 result에 temp.depth 넣고 return

for(int i = 0; i<4; i++)

{

//다음 위치의 좌표 계산한 nx, ny

if(map[nx][ny]==0) 안막혔으면

큐에 Data(nx, ny, temp.depth+1, temp.skill) 넣음

막혔으면서 스킬을 아직 안썼다면

큐에 Data(nx, ny, temp.depth+1, 1) 넣음. skill 써서 1

}

}

https://gist.github.com/dbwls94/e9f1a7bc00464c875a46009fda1f6248

[Code]

https://github.com/dbwls94/gomulsang/blob/youjin/BOJ/src/boj_2206/BreakingWall.java