이 문제 아무리 생각해도 더 이상 예외가 없는데.. 제가 빠트린게 있을까요?


appa   1년 전

이렇게 소스코드를 그냥 올리시는 것보단 방법을 적어주시는 게 좋습니다.

방법을 적다보면 본인이 깜빡한 경우를 알게될 수도 있죠. 그리고 무엇보다 답변자들이 답변하기가 수월합니다.

알겠습니다.

제 방법은..

priority queue를 만들고 bfs 탐색을 하였습니다.

queue의 data type은 <i,j,cnt> 로 되어 있습니다. 여기서 우선순위를 결정하는 것은 cnt(i,j까지 이동할 때까지 부순 벽 수) 이구요 i,j는 배열의 index가 됩니다.

탐색방법은 다음과 같습니다.

예를들어

0 1 1

0 1 1

1 0 0

과 같은 배열이 있을 때 아래 아래 오른쪽 오른쪽 으로 이동하는 경우가 가장 빠른 경우가 되겠죠.

제 알고리즘으로 탐색하는 경우 상 하 좌 우에 대한 배열값을 보며

i) 그 값이 1인 경우(막힌 경우) : priority_queue에 이동 할 i,j값과 현재까지의 cnt + 1의 값을 tuple로 묶어서 넣습니다.

벽을 하나 뚫어야 하기 때문에 cnt에 +1을 해줍니다.

ii) 그 값이 0인 경우(뚫린 경우) : priority_queue에 이동 할 i,j값과 현재까지의 cnt의 값을 tuple로 묶어서 넣습니다.

벽을 뚫을 필요가 없기 때문에 cnt를 그대로 넣어줍니다.

이렇게 탐색할 경우, priority_queue에는 cnt가 가장 작은 값을 먼저 빼기 때문에 결과적으로

0을 탐색할 수 있을 때까지 탐색하고 난 후 1을 탐색하게 됩니다.

실제로 위 배열 1,1에서 탐색한다고 하면,

처음 queue에 넣는 값은 <1,1,0> 이 되겠습니다. (시작위치와 끝 위치는 0이기 때문에 시작할 때 cnt를 0으로 줍니다.)

####현재 queue 내부 data {<1,1,0>}

<1,1,0>을 빼서 그 상하좌우를 탐색합니다. 상, 좌 는 이동할수 없기 때문에 제외시킵니다.

제 경우 visit 배열을 하나 더 두고 그 범위를 1칸씩 확장하여 boundary에 대한 예외처리를 하였습니다.

우 의 경우 <1,2,1> 입니다. 오른쪽의 배열값은 1이므로 벽을 하나 부수기 때문에 cnt가 1 증가합니다.

하 의 경우 <2,1,0> 입니다.

####현재 queue 내부 data {<1,2,1>, <2,1,0>}

priority queue에서는 우선순위가 가장 작은 값을 먼저 빼기 때문에 <2,1,0>이 빠집니다.

다시 <2,1,0>에 대한 상하좌우 중 가능한 값을 queue에 넣습니다. <2,2,1> <3,1,1>. visit 체크로 인해 이미 탐색한 경로는 무시합니다.

####현재 queue 내부 data {<1,2,1>, <2,2,1> <3,1,1>}

queue 내부 priority가 모두 1이므로 아무거나 뺍니다. <1,2,1>

<1,2,1>에 대한 상하좌우 중 visit이 한번도 되지 않은 오른쪽에 대한 data를 다시 넣습니다. <1,3,2>

####현재 queue 내부 data {<2,2,1> <3,1,1>,<1,3,2>}

<2,2,1>을 빼고 그에 대한 오른쪽, 아래 값을 다시 queue에 넣습니다. <2,3,2> <3,2,1>

####현재 queue 내부 data { <2,3,2> <3,2,1> <3,1,1>,<1,3,2>}

<3,1,1>을 빼고 상하좌우를 보지만 모두 이미 탐색했던 곳이므로 queue에 아무것도 넣지 않습니다.

####현재 queue 내부 data { <2,3,2>, <3,2,1> ,<1,3,2>}

<3,2,1>을 queue에서 빼고 가능한 위치인 오른쪽<3,3,1>을 queue에 넣습니다.

####현재 queue 내부 data { <2,3,2>, <3,3,1> ,<1,3,2>}

<3,3,1>을 queue에서 뺍니다. 이 지점은 도착 위치이므로 현재까지의 cnt(현재까지 부순 벽의 수) 를 time에 저장하고 while문을 나갑니다.

그렇게 하여 시작위치부터 도착위치까지 최소의 뚫어야하는 길 수를 구할 수 있습니다.

answer = 1

혹시 제가 생각하지 못한 예외가 있을까요? 아니면 제 logic에 문제가 있나요?

appa   1년 전

방법도 맞고, 제 컴퓨터에서 AC받은 소스와 함께 DM을 짜서 돌렸을 때, 랜덤데이터에서 10만개까지 똑같은 결과를 내놓네요...

잘 모르겠습니다.. 죄송합니다.

아닙니다. 그래도 제 logic도 나름 괜찮은가 보네요 ㅎㅎ

관심가져주셔서 감사합니다.

baekjoon   1년 전

N은 가로 크기이고, M은 세로 크기이다.

이 줄이 중요하네요... 문제에 예제를 하나 더 추가할게요

헐 ... 그걸 못보다니..

그런데 (N, M)으로 도착하도록 하면서 N이 가로크기이면 이상하지 않나요??

예를들어 N = 10 M = 5 로 준다고 하면, N이 가로고 M이 세로면

(M,N) 행렬이 되는데 여기서 N,M으로 도착하도록 하려면 배열범위 밖이지 않나요??

아 ... 애초에 여기서 얘기하는 (N, M)이라는게 배열의 (N,M)(행, 열) 이 아니라 (x,y)이군요...

제 실수가 맞네요..

감사합니다 ㅎㅎ

baekjoon   1년 전

그래서 문제를 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1을 벽을 의미한다. 로 수정했습니다.

댓글을 작성하려면 로그인해야 합니다.