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

(追記) (追記ここまで)

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

4485번 - 녹색 옷 입은 애가 젤다지?

jwl0105 3년 전 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;
}

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC