[C#] 아이템 줍기

프로그래머스 문제

https://school.programmers.co.kr/learn/courses/30/lessons/87694

풀이 후기

1. 분석

A*는 아니고... 사각형의 선분을 따라 탐색하는 문제. 단순해 보이지만 난이도는 좀 이상하다. 대충 배열로 잡고 탐색하면 겹치는 부분을 제외해야 하는데 그 부분이 좀 까다롭다.

일단 나는 배열로 돌리다가 뭔가 꼬이고 망해서 배열 대신에 그래프로 만들어서 점에서 점으로 이동하면서 탐색하는 방식으로 변경했다. 그래프로 보면 이해하기 더 쉬워지는 느낌. 그리고 사각형을 내부에 있는 점들은 이미 탐색한 것으로 처리해서 접근이 불가능하게 바꿨다.

2. 망함

그리고 죽음의 5번 케이스. 예제에 이런 케이스를 넣어주었다는 것에 감사합니다. 노랑 사격형 기준으로 직선으로 이동할 수 있지만, 붉은색 기준으로는 자기 자신을 뚫고 지나가는 선이라 이동이 불가능하다. 하필이면 한 칸이라서 저런 버그가 발생한다.

고민하다가 실패하고 결국 질문하기의 힘을 빌렸는데 그것은 바로...

for(int i = 0; i < rectangle.GetLength(0); i++)
{
    VisitedInRectangles((rectangle[i, 0] * 2, rectangle[i, 1] * 2), (rectangle[i, 2] * 2, rectangle[i, 3] * 2));
    ConnectingTwoPoints((rectangle[i,0] * 2, rectangle[i,1] *2 ), (rectangle[i,2] * 2, rectangle[i,3] * 2));
}

그냥 무식하게 점 개수를 2배로 늘리면 안 뚫린다. 테두리의 방향과 상성을 통해 최외각으로 이동하는 좋은 방법도 있던데, 머리 아파서 이번 문제는 여기까지...

3. 실행 결과

4. 코드

using System;
using System.Collections.Generic;

public class Solution {
    public Point[,] Points;

    public void VisitedInRectangles((int, int) a, (int, int) b)
    {
        for (int i = a.Item1 + 1; i < b.Item1; i++)
        {
            for (int j = a.Item2 + 1; j < b.Item2; j++)
            {
                Points[i, j].IsVisited = true;
            }
        }
    }
    
    public void ConnectingTwoPoints((int, int) a, (int, int) b)
    {
        var startX = a.Item1;
        var endX = b.Item1;
        var startY = a.Item2;
        var endY = b.Item2;

        while (startX < endX)
        {
            var startPoint1 = Points[startX, startY];
            var nextPoint1 = Points[startX + 1, startY];
            
            var startPoint2 = Points[startX, endY];
            var nextPoint2 = Points[startX + 1, endY];
            
            // startY 기준으로 점 2개를 연결
            startPoint1.ConnectPoint(nextPoint1);
            nextPoint1.ConnectPoint(startPoint1);
            
            // endY 기준으로 점 2개를 연결
            startPoint2.ConnectPoint(nextPoint2);
            nextPoint2.ConnectPoint(startPoint2);
            
            startX++;
        }
        
        startX = a.Item1;
        endX = b.Item1;
        startY = a.Item2;
        endY = b.Item2;
        
        while (startY < endY)
        {
            var startPoint1 = Points[startX, startY];
            var nextPoint1 = Points[startX, startY + 1];
            
            var startPoint2 = Points[endX, startY];
            var nextPoint2 = Points[endX, startY + 1];
            
            // startX 기준으로 점 2개를 연결
            startPoint1.ConnectPoint(nextPoint1);
            nextPoint1.ConnectPoint(startPoint1);
            
            // endX 기준으로 점 2개를 연결
            startPoint2.ConnectPoint(nextPoint2);
            nextPoint2.ConnectPoint(startPoint2);
            
            startY++;
        }
    }

    public class Point
    {
        public int x;
        public int y;
        public int Count = 0;
        public bool IsVisited = false;
        public List<Point> lines = new List<Point>();

        public Point(int x, int y)
        {
            this.x = x;
            this.y = y;
        }

        public void ConnectPoint(Point b)
        {
            lines.Add(b);
        }
    }

    public int CalcAnswer(int px, int py, int ix, int iy)
    {
        var q = new Queue<Point>();
        var player = Points[px, py];
        player.IsVisited = true;
        q.Enqueue(Points[px, py]);

        while (0 < q.Count)
        {
            var point = q.Dequeue();
            
            for (var i = 0; i < point.lines.Count; i++)
            {
                var nextPoint = point.lines[i];
                
                if (nextPoint.IsVisited == false)
                {
                    nextPoint.IsVisited = true;
                    nextPoint.Count = point.Count + 1;
                    q.Enqueue(nextPoint);
                }
            }
        }

        return Points[ix, iy].Count / 2;
    }

    public int solution(int[,] rectangle, int characterX, int characterY, int itemX, int itemY)
    {
        int pointX = 200;
        int pointY = 200;
        Points = new Point[pointX, pointY];

        for (int i = 0; i < pointX; i++)
        {
            for (int j = 0; j < pointY; j++)
            {
                Points[i, j] = new Point(i, j);
            }
        }
        
        for(int i = 0; i < rectangle.GetLength(0); i++)
        {
            VisitedInRectangles((rectangle[i, 0] * 2, rectangle[i, 1] * 2), (rectangle[i, 2] * 2, rectangle[i, 3] * 2));
            ConnectingTwoPoints((rectangle[i,0] * 2, rectangle[i,1] *2 ), (rectangle[i,2] * 2, rectangle[i,3] * 2));
        }
        
        return CalcAnswer(characterX * 2, characterY * 2, itemX * 2, itemY * 2);
    }
}