코테 스터디 21일차 TIL + 오늘의 학습 키워드 DFS, BFS

- 오늘의 학습 키워드 깊이우선 탐색, 넓이 우선 탐색
- 공부한 내용 본인의 언어로 정리하기

Flood Fill  페인트 통 도구와 같은 기능의 알고리즘

시작 픽셀에서 시작해서 동일한 색상을 가진 인접 픽셀들은 모두 새로운 색으로 변경

상하좌우

원래 색상과 동일한 색상을 가진 픽셀만 변경

 

DFS 함수

현재 위치의 유효성 확인

  배열 경계를 벗어나지 않는지를 확인

 현재 픽셀이 원래 색상과 같은지 확인

 

 

수도 코드

function floodFill(img, sr, sc,newcolor):
	//원래 색상
    originalColor = img[sr][sc]
    
    //만약 원래 색상과 새 색상이 같으면 아무것도 안함
    		if originalColor == new Color;
            return image
            
    //DFS 함수 정의
    function dfs(r,c):
    	if(r<0 or r>=img.length or c<0 or c>= img[0].length or img[r][c]!=originalColor:
        return
        
        //현재 픽셀 색상 변경
        img[r][c] = newColor
        
        //상하 좌우 이동
         dfs(r+1, c)  // 아래
        dfs(r-1, c)  // 위
        dfs(r, c+1)  // 오른쪽
        dfs(r, c-1)  // 왼쪽
        
         // DFS 시작
        dfs(sr, sc)

        return image

 

- 오늘의 회고
  - 어떤 문제가 있었고, 나는 어떤 시도를 했는지

DFS 푸는데 애를 먹음 

  - 어떻게 해결했는지

dfs 재귀법으로 풀었는데 

dfs의 재귀법== stack으로 푸는 방법이나 거의 똑같다

DFS의 각 노드는 무조건 한번만 방문한다.

노드=  같은 색을 가진 픽셀

연결= 상하좌우 

연결된 컴포넌트= 같은 색으로 연결된 모든 픽셀들의 집합

  - 무엇을 새롭게 알았는지 BFS로 풀게 되면 큐를 사용해서 풀수 있다. DFS 스택 사용해서 푸는 방법도 있다.

알고리즘 테스트에서는 재귀 dfs를 많이 사용하지만 실제로는 스택 오버플로우 문제를 피하기 위해 반복적 방법 BFS나 

반복 dfs를 많이 사용한다.
  - 내일 학습할 것은 무엇인지