static int N, M;
static char board[750][750];
static int visit[750][750][2];
static queue<pair<int, int>> q;
//0: left down,
//1: right down,
//0: y, 1: x
static int dd[2][2] = {
1, -1,
1, 1
};
static bool cant_go(int y, int x)
{
if (y < 0 || y >= N)
return true;
if (x < 0 || x >= M)
return true;
if (board[y][x] == '0')
return true;
return false;
}
static int get_len(int y, int x, int dir)
{
if (cant_go(y, x))
return 0;
if (visit[y][x][dir])
return visit[y][x][dir];
int len = 1 + get_len(y + dd[dir][0], x + dd[dir][1], dir);
visit[y][x][dir] = len;
return len;
}
static int check(int y, int x)
{
int len1 = get_len(y, x, 0);
int len2 = get_len(y, x, 1);
int len = len1 < len2 ? len1 : len2;
for (; len > 1; len -= 1)
{
int cy = y + (len - 1), cx = x - (len - 1);
if (get_len(cy, cx, 1) < len)
continue;
cx = x + (len - 1);
if (get_len(cy, cx, 0) < len)
continue;
else
break;
}
return len;
}
static int __solution(void)
{
int ret = 0;
int min = N < M ? N : M;
int max = min / 2 + min % 2;
if (q.size() == N * M) //전부 1인 경우
ret = max;
else
{
while (q.size())
{
pair<int, int> cur = q.front();
q.pop();
int result = check(cur.first, cur.second);
if (result > ret)
ret = result;
if (ret == max)
break;
}
memset(visit, 0, sizeof(visit));
}
while (q.size())
q.pop();
return ret;
}
static int solution(void)
{
scanf("%d %d\n", &N, &M);
for (int y = 0; y < N; y++)
{
scanf("%s\n", board[y]);
for (int x = 0; x < M; x++)
{
if (board[y][x] == '1')
q.push({ y, x });
}
}
if (q.empty())
return 0;
return __solution();
}일단 사소하지만 내가 곧잘 실수 했던 부분에 대한 것이다.
2차원 배열 탐색 시에는 배열의 범위를 벗어나는 위치인지에 대한 확인이 먼저 필요하다.
그렇지 않으면, 잘못된 메모리 영역 침범으로 인해 segmentation falut로 인한 run time error가 발생하기 때문이다.
그래서 2차원 배열의 범위 체크가 배열에 접근하기 전에 먼저 선행되어야 한다.
그러나 위 코드를 작성하면서 이 부분에 대해 내가 잘못된 방식으로 코드를 작성하고 있었다.
x, y에 대한 체크를 하나의 if에서 하고 있었던 것이다. 아래와 같이 말이다.
if (x < 0 || x >= N || y < 0 || y >= N) //잘못된 방식,
fail;
일차원 배열에서 하던 걸 그대로 적용하고 있었다.
아래와 같이 조건을 바꾸면 틀리진 않는다.
if (x >= 0 && x < N && y >= 0 && y < N)
success;
그러나 함수 이름 자체가 cant_go() 이므로 갈 수 없으면 true가 반환되어야 하고, 문제 조건 상 갈 수 없는 경우도 있었기 때문에 조건을 하나하나 거르는 방식으로 위 함수를 작성하다 보니 오류가 있었던 것 같다.
일단 풀이 자체는 동적 계획법이 약간 적용되었다.
해당 위치에서 마름모의 한변의 최대 길이를 미리 구하는 것이다.
그리고 이차원 배열에서 다음과 같은 방향으로만 이동하기 때문에, {↙, ↘}
밑으로 이동하면서 해당 위치에서 출발하여 갖을 수 있는 최대 길이를 같이 구할 수 있기 때문이다.
그래서 먼저 1인 위치에서 ↙쪽과 ↘쪽 중 최소 길이를 구한다.
그리고 해당 길이 만큼 이동한 위치에서 해당 길이 만큼 해당 길이 만큼 길이를 갖는지 체크하여,
마름모를 갖는지 확인하는데, 여기서 더 생각해야할 부분이 있다.
위 경우에서 최상단 1을 기점으로 보면 마름모의 크기는 2가 되는 것이 맞다.
그러나 좌측 꼭지점의 1은 동남쪽으로 2의 길이를 갖는다. 즉, 마름모의 길이 1보다 커지는 것이다.
이를 통해 마름모의 좌,우측 꼭지점의 길이가 적어도 현재 체크하려는 마름모의 길이보다 크다면 상관이 없다는 것을 알 수 있다.
위 경우에서는 최상단 1은 3의 크기를 갖는 마름모를 갖을 수 있다.
그러나 이 좌, 우측의 1이 이를 충족해주지 않기 때문에 이를 사용 할 수 는 없다.
그래서 여기에서는 마름모의 길이를 2에서 1로 조정하여 다시 확인 해 보는 작업이 필요하게 된다.
이것이 check() 에서 for문을 도는 경우가 된다.
