내일배움캠프 8일차 TIL - 알고리즘 과제

오늘의 학습 키워드

재귀

 

공부한 내용

Flood_Fill 문제

구현 방법 : 알고리즘 해결을 위해 생각했던 것이 좌표를 리스트에 넣어놓고 상하좌우를 값이 같은지 체크하면서 반복하면서 뻗어가는 방식이었다.

문제 : 해당 과제에서의 문제가 발생한 부분은 리스트 안에 다음 타일의 중복체크를 안 해서 스택 오버 플로우가 발생했다. 해해결 : FloodFillNext 메서드에 중복체크하는 구문을 통해 이를 해결하였다.

* HashSet이 List보다 더 런타임 속도가 빨라서 이후에 수정하였다.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace sparta
{
    class Flood_Fill
    {
        // 2차원 배열이 주어지고 특정 좌표와 색이 주어진다.
        // 특정 좌표의 값을 바꾸는데 특정 좌표로부터 4차원(위,아래,왼,오른쪽)과
        // 연결되어있는 같은 값을 모두 color의 숫자로 바꾼다.
        static void Main(string[] args)
        {
            FloodFill(new int[][] { new int[] { 1, 1, 1 }, new int[] { 1, 1, 0 }, new int[] { 1, 0, 1 } }, 1, 1, 2);

        }

        private static void FloodFill(int[][] image, int sr, int sc, int color)
        {
            HashSet<(int, int)> posSet = new HashSet<(int, int)>();
            posSet.Add((sr, sc));
            FloodFillNext(image, posSet, sr, sc);

            foreach (var item in posSet)
            {
                image[item.Item1][item.Item2] = color;
            }

            //return image;
        }

        private static void FloodFillNext(int[][] image, HashSet<(int, int)> posSet, int sr, int sc)
        {
            int next = -1;

            if (sr > 0 && image[sr][sc] == image[sr - 1][sc])
            {
                next = sr - 1;
                if (!posSet.Contains((next, sc)))
                {
                    posSet.Add((next, sc));
                    FloodFillNext(image, posSet, next, sc);
                }

            }
            if (sr + 1 < image.Length && image[sr][sc] == image[sr + 1][sc])
            {
                next = sr + 1;
                if (!posSet.Contains((next, sc)))
                {
                    posSet.Add((next, sc));
                    FloodFillNext(image, posSet, next, sc);
                }
            }
            if (sc > 0 && image[sr][sc] == image[sr][sc - 1])
            {
                next = sc - 1;
                if (!posSet.Contains((sr, next)))
                {
                    posSet.Add((sr, next));
                    FloodFillNext(image, posSet, sr, next);
                }
            }
            if (sc + 1 < image[0].Length && image[sr][sc] == image[sr][sc + 1])
            {
                next = sc + 1;
                if (!posSet.Contains((sr, next)))
                {
                    posSet.Add((sr, next));
                    FloodFillNext(image, posSet, sr, next);
                }
            }
        }
    }
}

https://leetcode.com/problems/flood-fill/description/

Flood Fill - LeetCode

 

 

오늘의 회고

 오늘은 알고리즘 강의와 여러 알고리즘 문제들을 풀면서 공부하는 시간을 가졌다. 아직 많이 모자라고 부족한 점도 많지만 문제를 분석하고 정리해둔 후 코드로 바꾼다는 접근법을 알게된 것만으로 많이 배웠다고 생각한다. 알고리즘 풀 때는 비슷한 유형의 문제들을 연속적으로 풀어서 그 유형에 익숙해지도록 해야겠다.

 강의 과제로 문제들을 풀면서 힌트도 보고 했는데 내일은 힌트를 보지 않고 강의에 나온 문제들을 다시 복습하는 시간을 가져야겠다. 내일도 파이팅!