733. Flood Fill

  • dfs 접근 법을 사용했고, number of islands 와 유사하나, 시작점의 색깔과 동일한 색깔만 바꾼다는 조건이 추가되어 있긴 하다.
  • 오타, 대소문자를 꼼꼼히 살필것. int 를 init 으로 쓴다거나,  newColor 를 newcolor 로 써서 compile error  가 났다. 이를 제외하고는 한번에 accept.
  • matrix 가 MxN  이라고 하면,  최악의 경우 모든 배열을 바꿔야하므로,  시간 복잡도는 O(MN)  이 된다. 

  • 간단한 문제여서 더 쓸건 없지만, 만약 BFS 로 접근해야 한다면 어떻게 해야할까? 
  • 자주 했었는데,  Queue 를 쓰면 된다. java 에서 Queue 구현은 LinkedList 로 되어 있다. 
  • 따라서 맨처음 주어진 포인트를 Queue 에 넣고, 뽑아서 체크하고, 4방향의 포인트들을 다시 queue 에 넣고. 이런식으로 해서 queue  가 텅 빌때까지 돌면 된다. 
  • 이 경우 queue 에 넣을 때 4방향 포인트를 다 넣을 필요 없이, 주어진 조건에 부합해서 색을 변경한 경우에만 넣으면 된다. 



Comments

Popular posts from this blog

삼성전자 무선사업부 퇴사 후기

개발자 커리어로 해외 취업, 독일 이직 프로세스

코드리뷰에 대하여