글 읽기 - 테스트케이스 4번...

moyoungmin 3년 전 0

왜 이방식이 틀린지 모르겠어서 질문드립니다... ㅠㅠ

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
#include <limits.h>
using namespace std;

int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };

void print(int tmp[21][21], int n) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << tmp[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

struct cordinate {
	int x;
	int y;
	int count;
	int length;
};

int main() {
	int n;
	int value[21][21];
	int check[21][21];
	cordinate shark;

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> value[i][j];
			
			if (value[i][j] == 9) {
				shark.x = j;
				shark.y = i;
				shark.count = 0;
				shark.length = 2;
				value[i][j] = 0;
			}
		}
	}
	
	int answer = 0;
	while (true) {
		queue<cordinate> q;
		memset(check, -1, sizeof(check));
		
		q.push(shark);
		check[shark.y][shark.x] = 0;

		while (!q.empty()) {
			cordinate front = q.front();	q.pop();

			for (int i = 0; i < 4; i++) {
				int nx = front.x + dx[i];
				int ny = front.y + dy[i];

				if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
					if (check[ny][nx] == -1 && value[ny][nx]<=front.length) {
						cordinate newValue;
						newValue.x = nx;
						newValue.y = ny;
						newValue.length = front.length;
						newValue.count = front.count;

						q.push(newValue);
						check[ny][nx] = check[front.y][front.x] + 1;
					}
				}
			}
		}
		// 아기상어위치로부터 BFS 수행
		
		int result = INT_MAX;
		int nx, ny;
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (value[i][j] != 0 && value[i][j] != 9 && check[i][j] != -1 && value[i][j]<shark.length) {
					if (result > check[i][j]) {
						nx = j;
						ny = i;
						result = check[i][j];
					}
				}
			}
		}
		// 최소 값을 가지는 nx, ny를 뽑음

		if(result == INT_MAX) {
			cout << answer << endl;
			return 0;
		}
		// 갈 곳이 없으니 프로그램 종료

		shark.count++;
		if (shark.count == value[ny][nx]) {
			shark.length++;
		}

		shark.x = nx;
		shark.y = ny;
		value[ny][nx] = 0;
		answer += check[ny][nx];
		// 상어 크기 처리

		cout << answer<<" "<<shark.length << endl;
		cout << "물고기 좌표" << endl;
		print(value, n);
		cout << "체크 여부" << endl;
		print(check, n);
		cout << endl;
	}
}

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

문제

문제

출처

ICPC

테스트케이스 4번...

moyoungmin 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말