글 읽기 - 2665 제 소스가 왜 맞는지 모르겠습니다

yukariko 9년 전 0

제가 생각한 알고리즘은 우선 n*n 크기의 point배열을 선언하고, 값을 max로 초기화합니다.

그 다음 point[1][1] 부터 point[n][n] 까지 반복하면서 point[i][j] 값을, point[i][j]. point[i-1][j], point[i][j-1] 사이의 최소값을 고른 후,

현재 위치가 만약 막혀있는 방이면 +1 해주도록 하고 반복이 끝나면 point[n][n]을 호출하는 방식입니다.

여기서 문제는 초기값입니다. 처음엔 단순히 point[1][1] = 0 으로만 두고 시작하니 틀림을 받았습니다.

그 다음 첫줄 가로,세로 부분만 따로 먼저 구해주고 시작을 했는데 역시 틀림을 받았습니다.

그런데 재귀를 통해서 1,1 하고 연결된 부분만 0으로 설정 해주니 ACCEPT를 받았습니다.

제가 풀어놓고도 이해가 잘 안가네요.. 어째서 저게 정답이 되는걸까요?

운좋게 데이터가 맞아떨어진게 아닌지 의심도 됩니다.

왜 정답인것인지 답변 해주시면 감사하겠습니다.

char map[51][51];
int n;
#define min(a,b) (a>b?b:a)
f(i,j)
{
  if(map[i][j]==2)return;
  map[i][j]=2;
  if(i<n&&map[i+1][j])f(i+1,j);
  if(i>1&&map[i-1][j])f(i-1,j);
  if(j<n&&map[i][j+1])f(i,j+1);
  if(j>1&&map[i][j-1])f(i,j-1);
}
main()
{
  int i,j;
  unsigned char point[51][51];
  scanf("%d",&n);
  for(i=1;i<=n;i++)
  {
    for(j=1;j<=n;j++)
    {
      scanf(" %c",&map[i][j]);
      map[i][j]-=48;
    }
  }
  f(1,1);
  for(i=1;i<=n;i++)
  {
    for(j=1;j<=n;j++)
    {
      point[i][j]=map[i][j]==2?0:255;
    }
  }
  for(i=1;i<=n;i++)
  {
    for(j=1;j<=n;j++)
    {
      if(j>1)point[i][j]=min(point[i][j],point[i][j-1]);
      if(i>1)point[i][j]=min(point[i][j],point[i-1][j]);
      point[i][j]+=!map[i][j];
    }
  }
  printf("%d",point[n][n]);
}

adream 9년 전 0

저도 잘 이해가 안가네요..제출하면 맞긴 하는데 ..


	1

joonas 9년 전 0

100111

001111

101000

101001

111001

아래로 갔다가 위로 올라가는 경우가 안되네요. 저도 그렇게 생각했다가 반례를 찾아서 새로운걸 생각하고 있었는데 맞아서 부럽네요

위 입력대로라면 2가 나오셔야하는데 1이 나오시네요. (전 3이 나오는 소스였는데 ㅠ) 데이터 확인이 필요한 것 같네요.

...는 바로 옆에서 글을 쓰는 @yukariko

joonas 9년 전 0

똑같은 소스같은데 나는 오답이라니 억울하다!!

pichulia 9년 전 1

11111011

00000001

11111101

10000000

11111111

이렇게 생긴 맵의 경우 답이 2이여야하는데

님의 코드로는 3이 나올거같네요...

왜냐하면 미로는

(i,j) -> (i,j+1) or (i+1,j) 로만 이동하는게 아니라

(i,j-1) 이랑 (i-1,j) 으로도 이동할 수 있는데

현재 작성한 코드는 위나 왼쪽으로 이동하는 경우는 고려하지 못하는 상황이네요..ㅋㅋㅋㅋ

저 소스코드가 맞은건 그냥 우연인듯....

adream 9년 전 0

아하!

yukariko 9년 전 0

제가 예전부터 쓸모없는 운은 좋더라구요..

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2665 제 소스가 왜 맞는지 모르겠습니다

yukariko 9년 전 0

adream 9년 전 0

joonas 9년 전 0

joonas 9년 전 0

pichulia 9년 전 1

adream 9년 전 0

yukariko 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말