728x90
반응형
런타임에러
요즘 왜 자꾸 런타임에러가 뜨지
#include<vector>
#include <iostream>
#include<tuple>
#include<queue>
#include<map>
using namespace std;
typedef tuple<int,int,int> tp;
priority_queue<tp,vector<tp>,greater<tp>>pq;
vector<vector<int>>arr;
vector<vector<bool>>visited;
map<tp,tuple<int,int,int,int>>info;
int dr[4]={0,0,1,-1};
int dc[4]={1,-1,0,0};
int n,m;
vector<int>parent;
int find(int node){
if(parent[node]<0)return node;
return parent[node]=find(parent[node]);
}
bool unions(int x,int y){
int xp=find(x);
int yp=find(y);
if(xp==yp)return false;
if(parent[xp]<parent[yp]){
parent[xp]+=parent[yp];
parent[yp]=xp;
}
else{
parent[yp]=parent[xp];
parent[xp]=yp;
}
return true;
}
void dfs(int i,int j,int num){
visited[i][j]=1;
arr[i][j]=num;
for(int k=0;k<4;k++){
int nr=i+dr[k];
int nc=j+dc[k];
if(nr<0 || nr>=n || nc<0 || nc>=m)continue;
if(!visited[nr][nc] && arr[nr][nc]==1){
dfs(nr,nc,num);
}
}
}
int main()
{
cin>>n>>m;
parent.assign(n+1,-1);
arr.assign(n,vector<int>(m,0));
visited.assign(n,vector<bool>(m,false));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>arr[i][j];
}
}
//섬을 지정하기
int num=1;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(!visited[i][j] && arr[i][j]==1){
dfs(i,j,num);
num++;
}
}
}
//만들수 있는 다리목록 - (거리,a,b) / 시작점 끝점
// i,j에서 시작하는 가로,세로다리
//양끝에 섬,길이 2이상
vector<tp>dist;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(arr[i][j]!=0)continue;
int a=arr[i][j-1];
int cnt=0;
int b;
int l;
bool flag=false;
//가로
if(j>0 && j<m-1){
for(int k=j;k<m;k++){
if(arr[i][k]==0)cnt++;
else{
if(a!=0 && arr[i][k]!=a && cnt>1){
b=arr[i][k];
flag=true;
l=k-1;
}
break;
}
}
if(flag && cnt>=2){
//거리, 두 섬 번호 , 시작점, 끝점
pq.push({cnt,a,b});
info[{cnt,a,b}]={i,j,l,0};
}
}
if(i>0 && i<n-1){
//세로
a=arr[i-1][j];
cnt=0;
flag=false;
for(int k=i;k<n;k++){
if(arr[k][j]==0)cnt++;
else{
if(a!=0 && arr[k][j]!=a && cnt>1){
b=arr[k][j];
flag=true;
l=k-1;
}
break;
}
}
if(flag && cnt>=2){
//거리, 두 섬 번호 , 시작점, 끝점
pq.push({cnt,a,b});
info[{cnt,a,b}]={i,j,l,1};
}
}
}
}
//모든 섬 연결하는 mst, 없으면 x
int c=0;
int answer=0;
while(c<(num-1)){
if(pq.empty()){
break;
}
int w=get<0>(pq.top());
int a=get<1>(pq.top());
int b=get<2>(pq.top());
pq.pop();
if(unions(a,b)){
c++;
int f=get<0>(info[{w,a,b}]);
int e=get<1>(info[{w,a,b}]);
int g=get<2>(info[{w,a,b}]);
int d=get<3>(info[{w,a,b}]);
if(d==0){ //가로
answer+=(g-e+1);
}
else{
answer+=(g-f+1);
}
}
}
if(c==(num-2))cout<<answer;
else cout<<-1;
return 0;
}
런타임에러가 나는 이유를 찾았다!!
섬의겟수인 num만큼 parent를 할당해야했는데 지도인 n으로 습관적으로 한것이었다..
#include<vector>
#include <iostream>
#include<tuple>
#include<queue>
#include<map>
using namespace std;
typedef tuple<int, int, int> tp;
priority_queue<tp, vector<tp>, greater<tp>>pq;
vector<vector<int>>arr;
vector<vector<bool>>visited;
map<tp, tuple<int, int, int, int>>info;
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
int n, m;
vector<int>parent;
int find(int node) {
if (parent[node] < 0)return node;
return parent[node] = find(parent[node]);
}
bool unions(int x, int y) {
int xp = find(x);
int yp = find(y);
if (xp == yp)return false;
if (parent[xp] < parent[yp]) {
parent[xp] += parent[yp];
parent[yp] = xp;
}
else {
parent[yp] = parent[xp];
parent[xp] = yp;
}
return true;
}
void dfs(int i, int j, int num) {
visited[i][j] = 1;
arr[i][j] = num;
for (int k = 0; k < 4; k++) {
int nr = i + dr[k];
int nc = j + dc[k];
if (nr < 0 || nr >= n || nc < 0 || nc >= m)continue;
if (!visited[nr][nc] && arr[nr][nc] == 1) {
dfs(nr, nc, num);
}
}
}
int main()
{
cin >> n >> m;
arr.assign(n, vector<int>(m, 0));
visited.assign(n, vector<bool>(m, false));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> arr[i][j];
}
}
//섬을 지정하기
int num = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && arr[i][j] == 1) {
dfs(i, j, num);
num++;
}
}
}
parent.assign(num+1, -1); //이거였음
//만들수 있는 다리목록 - (거리,a,b) / 시작점 끝점
// i,j에서 시작하는 가로,세로다리
//양끝에 섬,길이 2이상
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] != 0)continue;
int a;
int cnt = 0;
int b;
int l;
bool flag = false;
//가로
if (j > 0 && j < m - 1) {
a = arr[i][j - 1];
for (int k = j; k < m; k++) {
if (a == 0)break;
if (arr[i][k] == 0)cnt++;
else {
if (arr[i][k] != a && cnt > 1) {
b = arr[i][k];
flag = true;
l = k - 1;
}
break;
}
}
if (flag && cnt >= 2) {
//거리, 두 섬 번호 , 시작점, 끝점
pq.push({ cnt,a,b });
info[{cnt, a, b}] = { i,j,l,0 };
}
}
if (i > 0 && i < n - 1) {
//세로
a = arr[i - 1][j];
cnt = 0;
flag = false;
for (int k = i; k < n; k++) {
if (a == 0)break;
if (arr[k][j] == 0)cnt++;
else {
if (arr[k][j] != a && cnt > 1) {
b = arr[k][j];
flag = true;
l = k - 1;
}
break;
}
}
if (flag && cnt >= 2) {
//거리, 두 섬 번호 , 시작점, 끝점
pq.push({ cnt,a,b });
info[{cnt, a, b}] = { i,j,l,1 };
}
}
}
}
//모든 섬 연결하는 mst, 없으면 x
int c = 0;
int answer = 0;
while ( c < (num - 1)) {
if (pq.empty())break;
int w = get<0>(pq.top());
int a = get<1>(pq.top());
int b = get<2>(pq.top());
pq.pop();
if (unions(a, b)) {
c++;
int f = get<0>(info[{w, a, b}]);
int e = get<1>(info[{w, a, b}]);
int g = get<2>(info[{w, a, b}]);
int d = get<3>(info[{w, a, b}]);
if (d == 0) { //가로
answer += (g - e + 1);
for (int aa = e; aa <= g; aa++) {
arr[f][aa] = 9;
}
}
else {
answer += (g - f + 1);
for (int aa = f; aa <= g; aa ++) {
arr[aa][e] = 9;
}
}
}
}
if (c < (num - 2))cout << -1;
else cout << answer;
return 0;
}
728x90
반응형
'하루 1문제 챌린지 > Gold1' 카테고리의 다른 글
백준 2307번 도로검문 (C++,최단경로 역추적) (0) | 2024.06.20 |
---|---|
백준 8980번 택배(C++)🚩 (0) | 2024.03.15 |