2일차 - Ladder2
https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=4&contestProbId=AV14BgD6AEECFAYh&categoryId=AV14BgD6AEECFAYh&categoryType=CODE&problemTitle=&orderBy=SUBMIT_COUNT&selectCodeLang=ALL&select-1=4&pageSize=10&pageIndex=2
이문제 2시간넘게 왜틀린지 모르겟음.
10X10배열에서 내가 인풋 넣은건 이상없으나,
그이상 진행이 되지 않음...
답이 다르게 나온다.
백트래킹으로 다시 풀어봐야 한다
디버깅 할때 100x100으로 해야되는데 cmd창에 올라가질 않는다...
일단 실패했음.
#include <iostream>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int arr[100][100] = { 0, };
int visit[100][100] = { 0, };
int dx[3] = { 1,-1,0 };//기본 우-> 좌 -> 밑으로
int dy[3] = { 0,0,1 };
typedef struct {
int x;
int xpath_Cnt;
}max_struct;
vector<max_struct> vTemp;
int answer;
void bfs(int y, int x)
{
int path_length = 1;
queue<pair<int, int>> qTemp;
qTemp.push(make_pair(y, x));//
visit[y][x] = 1;
while (!qTemp.empty())
{
int iTempy = qTemp.front().first;
int iTempx = qTemp.front().second;
qTemp.pop();
for (int i = 0; i < 3; i++)
{
int ny = iTempy+dy[i];
int nx = iTempx+dx[i];
if (ny >= 0 && ny < 100 && nx >= 0 && nx < 100)//기본 사각 바운더리
{
if (ny == 99 && arr[ny][nx] == 1)
{
max_struct mxTempStruct;
mxTempStruct.x = x;
mxTempStruct.xpath_Cnt = path_length;
vTemp.emplace_back(mxTempStruct);
return;
}
if ((arr[ny][nx] == 1 && visit[ny][nx] == 0))//0이고 방문 안했으면
{
visit[ny][nx] = 1;
qTemp.push(make_pair(ny, nx));
path_length++;
break; //이 break를 통해 우 좌 하강에서 여러개 안하고 그냥 하나만한다.
}
}
}
}
return ;
}
void clear_all()
{
for (int i = 0; i < 100; i++)
{
for (int j = 0; j < 100; j++)
{
arr[i][j] = 0;
visit[i][j] = 0;
}
}
vTemp.clear();
answer = 0;
}
void clear_visit()
{
for (int i = 0; i < 100; i++)
{
for (int j = 0; j < 100; j++)
{
visit[i][j] = 0;
}
}
}
int main() {
int test_case;
for (test_case = 0; test_case < 10; test_case++)
{
clear_all();
int iCnt(0);
cin >> iCnt;
for (int i = 0; i < 100; i++)
{
for (int j = 0; j < 100; j++)
{
cin >> arr[i][j];
}
}
for (int i = 0; i < 100; i++)
{
if (arr[0][i] == 1)
{
bfs(0, i);
clear_visit();
}
}
sort(vTemp.begin(), vTemp.end(), [](max_struct a, max_struct b) {
if(a.xpath_Cnt == b.xpath_Cnt)
{
return a.x > b.x;
}
else
{
return a.xpath_Cnt > b.xpath_Cnt;
}
});
//출력
cout << "#" << test_case+1 << " " << vTemp[0].x << endl;
}
//종료
return 0;
}
Author And Source
이 문제에 관하여(2일차 - Ladder2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@imalive77/2일차-Ladder2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)