구름톤 챌린지 3주 day12 학습 일기

React Fragment Short Syntax 포스트잇과 귀여운 핑크 백팩 획득!

..답이.. 왜 2지?

 

처음 문제를 읽었을 때, 풀이 과정에서 발전기 위치를 지정해줘야 하는 것으로 생각해서

2개를 열심히 배치해보았지만 최소 3개가 필요한데.. 왜 2일까.. 하는 의문과,

이걸 찾을수가 있는건가? 이진탐색으로 최소 개수를 접근해도.. 배치하는 위치를 전부 고려하는게, 1,000,000,000 안에서 가능한걸까? 너무.. 어렵지 않나..? 하는 생각을 하면서

 

무언가 잘못 이해했다는 것을 알았다.

 

[제대로 이해한 내용]

해당 지점에 집이 있지만 발전기가 없어도, 그 집의 상하좌우 집 중 하나에 '전력을 공급받고 있다면' 해당 지점도 전력이 공급된다.

결국 발전기가 있는 집과 딱 붙어있지 않아도 된다는 의미.

발전기가 있는 집(3행2열)

발전기가 있는 집의 좌우 집들(3행1열,3행3열)은 전력을 공급받는다

그리고 전력을 공급받은 집(3행1열)과 인접한 집(2행1열)도 전력을 공급받는다

bfs 문제풀이

 

이렇게 집들이 이어져있기만 한다면, 이어진 집들 중 한 집만 발전기를 소유하면 된다.

따라서,

 

시작 지점을 설정하고,

bfs로 집이 있는지, 방문하지 않았는지 여부를 확인하고 방문 체크를 한 뒤

발전기 개수를 늘려주면 된다.

 

프로그래머스의 경우 예시 테스트 케이스에 대한 설명을 제시하는 방식이어서, 이해하기 어려운 예시 테스트 케이스라고 하더라도 설명을 보고 이해할 수 있는데

구름의 경우는 스스로 예시 테스트 케이스를 파악해야 해서 좀 더 문제를 꼼꼼히 읽어보고, 내가 가정한 내용과 차이가 있는 부분을 찾아내는 연습을 해야겠다.

 

오늘의 학습 일기 끝!