글 읽기 - 두 코드의 차이점을 모르겠습니다..ㅠㅠ

jwl0105 1년 전 0

이 문제를 풀어보면서 dp도 사용해보고 bfs도 풀어보고 그랬는데.. 그래도 정답이 안 나와서 구글링을 통해 공부하고 있었습니다.

제가 보기에는 구글링 코드와 다른 점이 없어 보이는데 구글링 코드는 정답이고, 제 코드는 오답이라고 나와서 계속 보고 있는데 아무리 봐도 모르겠습니다.. ㅠㅠ

한번만 도와주세요

https://gusdnr69.tistory.com/2...

//제 코드
#include <stdio.h>
int map[130][130], visited[130][130], move_x[4]={1,0,-1,0}, move_y[4]={0,1,0,-1}, front=0, rear=0, size=0, cnt=0;
typedef struct _Point
{
    int x, y;
}Point;
Point queue[50000], start;
void enqueue(Point n)
{
    queue[rear++]=n;
}
Point dequeue()
{
    return queue[front++];
}
void use_bfs()
{
    Point temp, next;
    while (front<rear)
    {
        temp=dequeue();
        for(int q=0; q<4; q++)
        {
            next.y=temp.y+move_y[q];
            next.x=temp.x+move_x[q];
            if (next.y>=0 && next.y<size && next.x>=0 && next.x<size)
            {
                if (visited[next.y][next.x] > visited[temp.y][temp.x]+map[next.y][next.x])
                {
                    visited[next.y][next.x] = visited[temp.y][temp.x]+map[next.y][next.x];
                    enqueue(next);
                }
            }
        }
    }
}
void clear()
{
    for(int a=0; a<size; a++)
    {
        for(int b=0; b<size; b++)
        {
            map[a][b]=0;
            visited[a][b]=0;
        }
    }
    front=0;
    rear=0;
}
int main()
{
    while(1)
    {
        scanf("%d", &size);
        if (size==0)
        break;
        cnt++;
        for(int i=0; i<size; i++)
        {
            for(int j=0; j<size; j++)
            {
                scanf("%d", &map[i][j]);
                visited[i][j]=2000000000;
            }
        }
        start.y=0;
        start.x=0;
        enqueue(start);
        visited[start.y][start.x]=map[start.y][start.x];
        use_bfs();
        printf("Promblem %d: %d\n", cnt, visited[size-1][size-1]);
        clear();
    }
}
// 구글링 코드

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int y_ar[4] = { 0,0,-1,1 };
int x_ar[4] = { 1,-1,0,0 };
int n;
int arr[130][130];
int dist[130][130];

void bfs() {

	queue <pair<int, int>> pq;

	pq.push(make_pair(0, 0));
	dist[0][0] = arr[0][0];
    
	while (!pq.empty()) {
		
		int y = pq.front().first;
		int x = pq.front().second;
		pq.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + y_ar[i];
			int nx = x + x_ar[i];
			

			if (ny >= 0 && ny < n && nx >= 0 && nx < n) {
				if ( dist[ny][nx] > dist[y][x] + arr[ny][nx]) {
					dist[ny][nx] = dist[y][x] + arr[ny][nx];
					pq.push(make_pair(ny, nx));
				}
			}
		}
	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int cnt = 1;

	while (1) {
		cin >> n;
		if (n == 0)
			break;

		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++) {
				cin >> arr[i][j];
				dist[i][j] = 2000000000;
			}
		
		bfs();
		cout << "Problem " << cnt++ << ": " << dist[n - 1][n - 1] << "\n";
	}

	return 0;
}

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

문제

문제

출처

ICPC

두 코드의 차이점을 모르겠습니다..ㅠㅠ

jwl0105 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말