코딩테스트 입문 - 안전지대 ( 2차원 배열 탐색 )

 

 

너무도 아름다운 너를,

너무도 반짝이는 너를,

나는 감히 위로하지 않는다.

 

너처럼 재미있는 사람을,

너처럼 반짝이는 사람을,

본 적이 없다고

 

부디 나의 사랑이

너에게 닿기를,

반짝이는 너에게,

아름다운 너에게,

 

 

 

어느 책 옮긴이가

독자에게 남겨준 글이 마음에 와닿아서 가져왔다.

 

가끔은

반짝이고, 재미있는 나여서

이렇게 지내도.. 괜찮을 거 같다는 생각도 들고..

 

한편으로는

이렇게 지내도 정말 괜찮을까..? 하는 걱정에

고치고, 달라지고 싶다는 생각도 든다.

---

 

 

아따... 어렵다...

이런 2차원 애들이 가장 싫다..

 

바로 인지 씨한테 가서 투정 부렸다.

 

인지 씨가 말하길 이 문제는

1. 맵 전체 훑기

2. 주변을 확인하기

3. 경고표시하기

4. 안전지대 세기

 

순서라고 했다.

가장 중요한 건..!

 8방향을 탐색할 수 있는 비밀무기가 필요하다고 했다.

 

순서는 알았는데...

비밀무기..?

이동좌표를 미리 배열로 만들어 두라고 했다.

8방향..

 

 

일단 배열의 사이즈를 알아야 한다.

2차원 배열은 사이즈를 어떻게 알 수 있을까?

board.size()로 알 수 있다.

 

엇.. 이차원인데?!

5칸이면 총 25개로 나오지 않으려나?

이것은 상자 안에 상자이기 때문에

 

아파트로 비교하면

너 몇 층 짜리야?

board.size()?  = 5

5층이야!

 

너 5층에 집 몇 채 있어?

board [4]. size()? = 5

5채!

이렇게 된다.

 

그래서 board.size() = n으로 잡고

모든 자리를 돌면서 1일 경우를 찾아야 한다.

 

자, 이제 1을 찾게 되면!

비로소 비밀무기를 꺼낸다.

 

int dx [8] = {-1, -1, 0, 1, 1, 1, 0, -1};

int dy [8] = {0, 1, 1, 1, 0, -1, -1, -1};

 

바로 이것!

이것은 방향 배열로

 

 

이 그림으로 더 쉽게 이해할 수 있을 것이다.

 

위쪽부터 시계방향으로 돌아가며

x값 y값을

i와 j값에다가 더하는 것이다.

즉 (dx, dy) 묶음을 만들기 위한 벡터이다.

시작부터 뱅글뱅글 돌아가줘야 하니까 for문을 써야 한다

 

삼중.. for문.. ㄷㄷ

 

그래서 세 번째 for문을 만들고

i + dx [k] 해준 값을 nx라고 새롭게 명명해 준다.

 

그다음에

nx 그리고 ny가 0보다 크고 n보다 작으면

즉 범위 안에 있으면 

그리고!

그 범위 안에서 0이면!!

 

위험한 지대라고 표시해 줍시다.

숫자는 뭐든 상관없습니다.

 

마지막으로 이제 새로운 이중포문으로

0 개수 세서 answer에 더해주면 된다.

 

 

 

wow 정말 긴 문제였다.

 

bfs? 랑 비슷한 문제인 거 같긴 했는데

약간 다르다고 한다.

 

이 문제가 2차원 배열 탐색 정석 코드라고 한다.

 

dx, dy 배열 미리 만들어주고,

2중 포문으로 모든 곳 다 돌면서

찾았을 때 for문 하나 더 써서 (8번) ( 총 3중 포문 )

dx, dy 더해준 nx, ny 만들어주고

nx, ny가 범위 안에 잘 있으면

주변 다 2로 만들어주고

 

마지막에 다시 이중포문으로 결괏값 더해주기.

---

 

 

이렇게 미치게 어려운데

1점이라니..

 

뭐가 단단히 잘못됐다.

 

하루 정말 고생 많았다.

이런 문제 이제는 어떻게 풀어야 할지 기억하는 것만으로도 충분하다.

그렇게 생각하자.

 

아!

그리고 잊지 말자

 

너처럼 재미있는 사람을,

너처럼 반짝이는 사람을,

본 적이 없다고

 

부디 나의 사랑이

너에게 닿기를,

반짝이는 너에게,

아름다운 너에게,