글 읽기 - 반례 부탁드립니다.

jwl0105 1년 전 0

도저히 봐도 모르겠습니다. 구글링을 해봐도 잘 모르겠습니다..

중복 방문을 생각해야한다고 해서 여러가지로 해봐도 나오지 않아서 진짜 한번 부탁드리겠습니다...ㅠㅠ

#include <stdio.h>
char map[301][301];
int visited[300][300], move_x[4]={1,0,-1,0}, move_y[4]={0,1,0,-1}, check_tp[26], front=0, rear=0, size_y=0, size_x=0;
typedef struct _Point
{
    int x, y;
}Point;
Point queue[100000], tp_start[26], tp_end[26], dest, start;
void enqueue(Point n)
{
    queue[rear++]=n;
}
Point dequeue()
{
    return queue[front++];
}
void use_bfs()
{
    Point temp, next, telpo_start, telpo_end;
    while (front<rear)
    {
        temp=dequeue();
        for(int q=0; q<4; q++)
        {
            next.x=temp.x+move_x[q];
            next.y=temp.y+move_y[q];
            if (next.y>=0 && next.y<size_y && next.x>=0 && next.x<size_x && visited[next.y][next.x]==0 && map[next.y][next.x]!='#')
            {
                if (map[next.y][next.x]>='A' && map[next.y][next.x]<='Z') // 방문 할 곳이 텔레포트인 경우
                {
                    telpo_start.y=tp_start[map[next.y][next.x]-'A'].y; // 텔레포트 양방향을 모두 저장
                    telpo_start.x=tp_start[map[next.y][next.x]-'A'].x;
                    telpo_end.y=tp_end[map[next.y][next.x]-'A'].y;
                    telpo_end.x=tp_end[map[next.y][next.x]-'A'].x;
                    if (visited[telpo_start.y][telpo_start.x]==0) // 만약 이미 방문했던 곳이라면 생각하지 않습니다. 
                    {
                        visited[telpo_start.y][telpo_start.x]=visited[temp.y][temp.x]+1;
                        enqueue(telpo_start);
                    }
                    if (visited[telpo_end.y][telpo_end.x]==0)
                    {
                        visited[telpo_end.y][telpo_end.x]=visited[temp.y][temp.x]+1;
                        enqueue(telpo_end);
                    }
                }
                else // 다음 위치가 '.'인 경우는 일반적인 방법으로 했습니다.
                {
                    visited[next.y][next.x]=visited[temp.y][temp.x]+1;
                    enqueue(next);
                }
            }
        }
    }
}
int main()
{
    char str[301];
    scanf("%d %d", &size_y, &size_x);
    for(int i=0; i<size_y; i++)
    {
        scanf("%s", str);
        for(int j=0; j<size_x; j++)
        {
            map[i][j]=str[j];
            if (map[i][j]>= 'A' && map[i][j] <= 'Z') // 해당 위치가 텔레포트인 경우, 양방향 이동이기 때문에 시작과 끝 위치를 저장
            {
                if (check_tp[map[i][j]-'A']==0) // 말은 시작과 끝이지만 나온 순서대로 시작과 끝입니다. 차이가 없습니다.
                {
                    tp_start[map[i][j]-'A'].y=i;
                    tp_start[map[i][j]-'A'].x=j;
                    check_tp[map[i][j]-'A']=1; // check_tp는 같은 알파벳이 나올 때 구별하기 위한 배열입니다.
                }
                else
                {
                    tp_end[map[i][j]-'A'].y=i;
                    tp_end[map[i][j]-'A'].x=j;
                }
            }
            else if (map[i][j]=='@') // 시작점 확인 후 바로 인큐
            {
                start.y=i;
                start.x=j;
                enqueue(start);
                visited[start.y][start.x]=1; // 시작점 1
            }
            else if (map[i][j] == '=') // 도착지 저장
            {
                dest.y=i;
                dest.x=j;
            }
        }
    }
    use_bfs();
    printf("%d", visited[dest.y][dest.x]-1); // 목적지를 가기 위한 거리 출력 (시작이 1이라서 그 값을 빼주기 위한 -1)
}

jwl0105 1년 전 0

풀었습니다.. ㅠㅠ

텔레포트 위치에 갈 때, (tel_s, tel_e라고 양 끝 점을 가정하겠습니다.)

만약 다음 위치가 tel_s일 때, tel_s는 방문하지 않고, tel_e만 간다고 하니 맞았습니다. (tel_s는 현재 위치 -> tel_e -> tel_s 방법을 이용해서 갈 수 있는 듯 합니다.)

이 부분을 처리하기 위해서 방문 여부는 bool visited[][]를 사용하고, 구조체에 int x, y, d(거리) 요소를 추가해서 풀었습니다.

저는 똑똑하지 않아서 방황했지만 여러분들은 참고하셨으면 좋겠습니다!

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

문제

문제

출처

ICPC

반례 부탁드립니다.

jwl0105 1년 전 0

jwl0105 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말