알고리즘] 2

 

친구가 준 문제2

 

N개의 열과 M개의 행으로 구성된 사각형 맵이 있는데, 각 영역은 특정 색으로 칠해져 있다.
맵의 두 영역은 다음 조건이 만족될 때 같은 나라에 포함된다.
같은 색을 가지고 있다.
다른 색으로 칠해진 영역을 거치지 않고, 동서남북 네 방향으로만 움직여서 한 영역에서 다른 영역으로 이동할 수 있다.
맵은 인덱스 0에서 시작하는 M열과 N행으로 구성된 정수들의 매트릭스로 기술될 수 있다. 각 영역의 색은 매트릭스의 각 요소로써 기술된다.
두 영역은 매트릭스의 각 요소가 같은 값을 가질 때에만 같은 색을 가진다.
예를 들어, 7열, 3행으로 구성된 매트릭스 A를 생각해보자.
A[0][0] = 5 A[0][1] = 4 A[0][2] = 4
A[1][0] = 4 A[1][1] = 3 A[1][2] = 4
A[2][0] = 3 A[2][1] = 2 A[2][2] = 4
A[3][0] = 2 A[3][1] = 2 A[3][2] = 2
A[4][0] = 3 A[4][1] = 3 A[4][2] = 4
A[5][0] = 1 A[5][1] = 4 A[5][2] = 4
A[6][0] = 4 A[6][1] = 1 A[6][2] = 1
매트릭스 A는 5가지 색으로 칠해진 맵으로 기술된다. 맵의 영역들은 7개의 다른 나라를 포함한다.
- A[0][0] 는 한 영역으로 구성된 하나의 나라를 형성한다.
- A[0][1], A[0][2], A[1][2], A[2][2]는 네 개의 영역으로 구성된 하나의 나라를 형성한다.
- A[1][0] 는 한 영역으로 구성된 하나의 나라를 형성한다.
- A[1][1] 는 한 영역으로 구성된 하나의 나라를 형성한다.
- A[2][0] 는 한 영역으로 구성된 하나의 나라를 형성한다.
- A[2][1], A[3][0], A[3][1], A[3][2] 는 네 개의 영역으로 구성된 하나의 나라를 형성한다.
- A[4][0], A[4][1] 는 두 개의 영역으로 구성된 하나의 나라를 형성한다.
- A[4][2], A[5][1], A[5][2] 는 세 개의 영역으로 구성된 하나의 나라를 형성한다.
- A[5][0] 는 한 영역으로 구성된 하나의 나라를 형성한다.
- A[6][0] 는 한 영역으로 구성된 하나의 나라를 형성한다.
- A[6][1], A[6][2] 는 두 개의 영역으로 구성된 하나의 나라를 형성한다.
함수를 작성해라.
def solution(A: Vector[Vector[Int]]): Int = {
 // TODO:
}
함수는 주어진 N열, M행의, 인덱스 0에서 시작하는 매트릭스 A에 대해서, 매트릭스 A에 의해 기술되는 맵의 영역들이 포함되는 나라의 수를 반환한다.
다음을 가정해라.
N은 범위 [1..300,000]의 정수이다.
M은 범위 [1..300,000]의 정수이다.
매트릭스 A의 요소 수는 범위 [1..300,000] 사이의 정수이다.
매트릭스 A의 각 요소의 값은 범위 [?1,000,000,000..1,000,000,000] 사이의 정수이다.
예를 들어, 위의 예에서, 7개의 열과 3개의 행으로 구성된 매트릭스 A에 대해서, 함수는 11을 반환해야만 한다.

 

풀이 )

    소요시간은 코딩시간 2시간, 고민시간 출퇴근 2시간 + 집에서 미드보면서 1시간...

    오래 걸리네...

 

Index = Row * ColCount + Col ;

격자의 Index로 루프를 돈다.

 

for{

1. Value = 0, Value와 현재 인덱스 값과 같은지 확인. 다르면 List에 등록 & 카운트

while(){

2. List에서 Index의 값 꺼내 Map의 현재 위치에서 좌, 우, 하 에 대한 Cell값 비교

3. 값이 같으면 List에 Index값 추가.

4. List의 다음 Index 값을 꺼내어 2번 ~ 3번 반복.

}

5. 같은 값이 없으면 리스트에 등록된 Index의 Cell 값에 * -1 적용.

6. 리스트 초기화

}

 

static void Main(string[] args)
{ 
    int[,] map = new int[,] {
        { 5, 4, 4},
        { 4, 3, 4},
        { 3, 2, 4},
        { 2, 2, 2},
        { 3, 3, 4},
        { 1, 4, 4},
        { 4, 1, 1},
    };
    int RowCount = map.GetUpperBound(0) + 1;
    int ColCount = map.GetUpperBound(1) + 1;
    int cnt = 0;
    int value = 0, row = 0, col = 0;
    int xMinus = 0, xPlus = 0, yPlus = 0;
    List<int> BufferIndex = new List<int>();

    bool IsFind = false;

    for (int idx = 0; idx < map.Length; idx++)
    {
        IsFind = false;
        value = 0;
        row = idx / ColCount; col = idx % ColCount;
        BufferIndex.Clear();
        if (value != map[row, col] && 0 < map[row, col])
        {
            value = map[row, col];
            BufferIndex.Add(idx); cnt++;
            IsFind = true;
        }

        while (IsFind)
        {
            if (value == 2)
            {
                int breakValue = 0;
            }
            IsFind = false;
            for (int i = 0; i < BufferIndex.Count; i++)
            {
                row = BufferIndex[i] / ColCount; col = BufferIndex[i] % ColCount;

                xMinus = col - 1;
                xPlus = col + 1;
                yPlus = row + 1;

                // -x;
                if (xMinus >= 0 &&

value == map[row, xMinus] &&

0 < map[row, xMinus] &&

!BufferIndex.Contains(row * ColCount + xMinus))
                {
                    BufferIndex.Add(row * ColCount + xMinus);
                    IsFind |= true;
                }
                // +x;
                if (xPlus < ColCount &&

value == map[row, xPlus] &&

0 < map[row, xPlus] &&

!BufferIndex.Contains(row * ColCount + xPlus))
                {
                    BufferIndex.Add(row * ColCount + xPlus);
                    IsFind |= true;
                }
                // +y;
                if (yPlus < RowCount &&

value == map[yPlus, col] &&

0 < map[yPlus, col] &&

!BufferIndex.Contains(yPlus * ColCount + col))
                {
                    BufferIndex.Add(yPlus * ColCount + col);
                    IsFind |= true;
                }
            }
        }

        for (int loop = 0; loop < BufferIndex.Count; loop++)
        {
            map[BufferIndex[loop]/ ColCount, BufferIndex[loop] % ColCount]*= -1;
        }
        Console.WriteLine("count=" + cnt);
        Print(map);
        Console.ReadLine();
        Console.Clear();
    }

    Console.WriteLine("count=" + cnt);
    Console.ReadLine();
}

static void Print(int[,] map)
{
    int RowCount = map.GetUpperBound(0) + 1;
    int ColCount = map.GetUpperBound(1) + 1;
    for (int r = 0; r < RowCount; r++)
    {
        Console.Write(r.ToString("D2")+"행 ");
        for (int c = 0; c < ColCount; c++)
        {
            Console.Write( map[r, c] + " ");
        }
        Console.WriteLine("");
    }
}