알고리즘/백준
백준 2146번 - 다리 만들기 C++
초심을 찾자
2023. 12. 5. 09:41
SMALL
2146번: 다리 만들기
여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다
www.acmicpc.net
나의 첫 알고리즘 Tistory 포스팅은 백준 2146번이다. 아래에 문제를 캡처해 두었다. 해당 포스팅을 보는 사람들은 단순 답만 궁금해서 들어올 수도 있지만 나는 내가 생각했던 방법들을 정리하고 무엇이 문제였는지까지 정리를 할 예정이다. 만약 답만 단순하게 궁금한 경우에는 가장 마지막 아이디어의 코드를 보면 될 것으로 예상을 한다.
이해한 문제 내용은 다음과 같다.
두 대륙(점수가 0)을 잇는 가장 짧은 다리를 찾아야 한다. 다만 이 다리는 대각선으로는 이동할 수 없으며, 무조건 좌상우하로만 움직일 수 있는 것 같다. 이와 같이 생각한 이유는 그림을 보면 3칸이 가장 짧은 다리라고 언급하였는데, 대각선이 허용되는 경우는 답이 2이기 때문에 이와 같이 판단하였다. 개인적으로 여기서 문제를 잘못 읽고 대각선으로 체크하여 오답을 제출하는 사람도 있을 것이라 생각이 든다.
Idea1 ) 나는 두 섬을 잇는다는 가장 중요한 포인트를 잊고 한 격자의 입장에서 방향성만 고려하여 가장 작은 숫자를 선택하는 방법을 택하려고 했다. 아래의 사진과 같이 2,2의 입장에서는 총 4가지의 방향에서 오는 경우의 수가 있기 때문에 방향별로 방문 여부 및 개수를 관리하고자 하였다. 다만 시작은 모든 점에서 다해보는 걸로 하였고, 그 결과 실패 한다는 것을 스스로 디버깅을 통해 알 수 있었다.
코드는 아래와 같이 구현하였는데 참고만 하면 좋을 것 같다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <string.h>
using namespace std;
const int DIRECTION_COUNT = 4;
const int MAX_VERTEX_COUNT = 101;
bool bVisited[MAX_VERTEX_COUNT][MAX_VERTEX_COUNT][DIRECTION_COUNT];
int iMapSize = 0;
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 };
int iMap[MAX_VERTEX_COUNT][MAX_VERTEX_COUNT][DIRECTION_COUNT];
enum eDirection {
DOWN = 0 ,
UP = 1,
RIGHT = 2,
LEFT = 3
};
eDirection directionList[DIRECTION_COUNT] = { eDirection::DOWN ,eDirection::UP,eDirection::RIGHT,eDirection::LEFT };
void FindShortPath(const eDirection& rDirection, const int& rCount, const int& rCurX, const int& rCurY)
{
if (true == bVisited[rCurX][rCurY][rDirection])
{
if (rCount < iMap[rCurX][rCurY][rDirection]) // 최솟값으로 적재 후 반환
{
iMap[rCurX][rCurY][rDirection] = rCount;
}
return;
}
iMap[rCurX][rCurY][rDirection] = rCount;
bVisited[rCurX][rCurY][rDirection] = true;
int tempX = 0, tempY = 0;
for (int i = 0; i < DIRECTION_COUNT; ++i)
{
tempX = dx[i] + rCurX;
tempY = dy[i] + rCurY;
if (tempX < 0 || tempX >= iMapSize || tempY < 0 || tempY >=iMapSize)
{
continue;
}
// 이말은 갈수 있는 곳이라는 의미
if (MAX_VERTEX_COUNT != iMap[tempX][tempY][0])
{
FindShortPath(directionList[i], rCount + 1, tempX, tempY);
}
}
}
int main() {
memset(bVisited, 0, sizeof(bVisited));
int iTInput = 0;
cin >> iMapSize;
for (int iRow = 0; iRow < iMapSize; ++iRow)
{
for (int iCol = 0; iCol < iMapSize; ++iCol)
{
cin >> iTInput;
if (1 == iTInput)
{
iMap[iRow][iCol][0] = MAX_VERTEX_COUNT; // 얘는 0번만 체크하면 되기 때문에 1,2,3은 굳이 적재하지 않아도됨
}
else
{
iMap[iRow][iCol][0] = MAX_VERTEX_COUNT - 1;
iMap[iRow][iCol][1] = MAX_VERTEX_COUNT - 1;
iMap[iRow][iCol][2] = MAX_VERTEX_COUNT - 1;
iMap[iRow][iCol][3] = MAX_VERTEX_COUNT - 1;
}
}
}
for (int iRow = 0; iRow < iMapSize; ++iRow)
{
for (int iCol = 0; iCol < iMapSize; ++iCol)
{
if (MAX_VERTEX_COUNT == iMap[iRow][iCol][0])
{
FindShortPath(eDirection::DOWN, 1, iRow, iCol);
}
}
}
return 0;
}
Idea2 ) Idea1에서 느꼈던 문제 해결을 위해 섬을 구분할 필요가 있다는 것을 느꼈고, 각 섬마다 모두 가장 짧은 다리를 찾기 위해 다 진행을 해보아야 한다는 점이었다. 간단하게 알고리즘 순서도는 아래와 같을 것 같다.
1.정보를 입력 받는다.
/************************************************
@함수명 : Input
@기능 : 입력을 받는 함수
@입력값 :
@출력값 :
@비고 :
*************************************************/
void Input()
{
for (int iRow = 0; iRow < iMapSize; ++iRow)
{
for (int iCol = 0; iCol < iMapSize; ++iCol)
{
cin >> iMap[iRow][iCol];
if (1 == iMap[iRow][iCol])
{
iMap[iRow][iCol] = -1;
}
}
}
}2.섬을 구분한다.
1. 섬을 구분하는 동시에 모서리 정보도 같이 저장한다.
/************************************************
@함수명 : CheckDuplicateValue
@기능 : 중복원소 체크
@입력값 : int - X 좌표
int - Y 좌표
@출력값 :
@비고 :
*************************************************/
void CheckDuplicateValue(const int& rX, const int& rY)
{
bool isExist = false;
for (auto iter = vEdgeList.begin() ; iter != vEdgeList.end() ; ++iter)
{
if ( rX == iter->first
&& rY == iter->second)
{
isExist = true;
break;
}
}
if (false == isExist)
{
vEdgeList.push_back(make_pair(rX, rY));
}
}
/************************************************
@함수명 : MakeLand_Number
@기능 : 입력을 받는 함수
@입력값 : int - 현재 X좌표
int - 현재 Y좌표
int - 섬 번호
@출력값 :
@비고 :
*************************************************/
void MakeLand_Number(const int& rX, const int& rY, const int& rLandNumber)
{
queue<pair<int, int>> qLandList; // 섬에 해당하는 좌표를 담을 공간
qLandList.push(make_pair(rX, rY)); // 최초로 받은 좌표 삽입
while (false == qLandList.empty())
{
int iCurX = qLandList.front().first;
int iCurY = qLandList.front().second;
qLandList.pop();
iMap[iCurX][iCurY] = rLandNumber; // 섬 번호 부여
int iJudgeEdgeCnt = 0; // 모퉁이를 찾기 위함
for (int i = 0; i < DIRECTION_COUNT; ++i)
{
int iTempX = iCurX + dx[i];
int iTempY = iCurY + dy[i];
if (0 > iTempX || iMapSize <= iTempX || 0 > iTempY || iMapSize <= iTempY) // 인덱스 범위 체크 Memory Corruption 방지
{
iJudgeEdgeCnt++;
continue;
}
if (0 > iMap[iTempX][iTempY]) // 방문이 가능하고, 섬인경우에만 후보리스트에 적재
{
qLandList.push(make_pair(iTempX, iTempY));
}
if (0 != iMap[iTempX][iTempY])
{
iJudgeEdgeCnt++;
}
}
if (DIRECTION_COUNT != iJudgeEdgeCnt)
{
CheckDuplicateValue(iCurX, iCurY);
}
}
}3. 모서리 개수만큼 아래 동작을 반복한다.
1.현재 서로 다른 섬의 모서리인 경우 두 모서리의 거리를 구한다.
1. 거리 계산식 : ABS(X2- X1) + ABS(Y2-Y1) - 1 ( 노트를 통해 한 번 계산해보기를 추천한다. )
2.가장 작은 값을 계속해서 최신화 한다.
/************************************************
@함수명 : CalculateShortestPath
@기능 : 가장 작은 거리를 찾는 함수
@입력값 :
@출력값 : int - 가장 작은 거리 값
@비고 :
*************************************************/
int CalculateShortestPath()
{
int iEdgeCount = static_cast<int>(vEdgeList.size());
int iAnswer = MAX_VERTEX_COUNT;
for (int iEIndex = 0; iEIndex < iEdgeCount - 1; ++iEIndex)
{
int curX = vEdgeList[iEIndex].first;
int curY = vEdgeList[iEIndex].second;
for (int iSubEIndex = iEIndex + 1; iSubEIndex < iEdgeCount; ++iSubEIndex)
{
int comX = vEdgeList[iSubEIndex].first;
int comY = vEdgeList[iSubEIndex].second;
if (iMap[curX][curY] != iMap[comX][comY]) // 서로 다른 섬이라는 것을 의미
{
int distance = abs(curX - comX) + abs(curY - comY) - 1;
if (iAnswer > distance)
{
iAnswer = distance;
}
}
}
}
return iAnswer;
}
4.가장 작은 값을 출력한다.
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> iMapSize;
Input();
vEdgeList.reserve(25);
int iLandNum = 1; // 1부터 시작하는 이유는 섬의 구분자가 1이기 때문에 0부터 시작은 할 수가 없음
for (int iRow = 0; iRow < iMapSize; ++iRow)
{
for (int iCol = 0; iCol < iMapSize; ++iCol)
{
if (0 > iMap[iRow][iCol])
{
MakeLand_Number(iRow, iCol, iLandNum);
iLandNum++;
}
}
}
cout << CalculateShortestPath();
return 0;
}
하지만 이렇게 풀었을 경우 메모리초과가 발생하였다... 계속해서 시도 중이지만 근본적인 원인은 찾지못하였다. 혹시 해당 포스팅을 보고 문제점이 먼지 지적을 해줄수 있는 분이 계신다면 댓글부탁드립니다!
전체 코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <string.h>
using namespace std;
const int DIRECTION_COUNT = 4;
const int MAX_VERTEX_COUNT = 100;
vector<pair<int, int>> vEdgeList;
int iMapSize = 0;
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 };
int iMap[MAX_VERTEX_COUNT][MAX_VERTEX_COUNT];
/************************************************
@함수명 : CheckDuplicateValue
@기능 : 중복원소 체크
@입력값 : int - X 좌표
int - Y 좌표
@출력값 :
@비고 :
*************************************************/
void CheckDuplicateValue(const int& rX, const int& rY)
{
bool isExist = false;
for (auto iter = vEdgeList.begin() ; iter != vEdgeList.end() ; ++iter)
{
if ( rX == iter->first
&& rY == iter->second)
{
isExist = true;
break;
}
}
if (false == isExist)
{
vEdgeList.push_back(make_pair(rX, rY));
}
}
/************************************************
@함수명 : Input
@기능 : 입력을 받는 함수
@입력값 :
@출력값 :
@비고 :
*************************************************/
void Input()
{
for (int iRow = 0; iRow < iMapSize; ++iRow)
{
for (int iCol = 0; iCol < iMapSize; ++iCol)
{
cin >> iMap[iRow][iCol];
if (1 == iMap[iRow][iCol])
{
iMap[iRow][iCol] = -1;
}
}
}
}
/************************************************
@함수명 : MakeLand_Number
@기능 : 입력을 받는 함수
@입력값 : int - 현재 X좌표
int - 현재 Y좌표
int - 섬 번호
@출력값 :
@비고 :
*************************************************/
void MakeLand_Number(const int& rX, const int& rY, const int& rLandNumber)
{
queue<pair<int, int>> qLandList; // 섬에 해당하는 좌표를 담을 공간
qLandList.push(make_pair(rX, rY)); // 최초로 받은 좌표 삽입
while (false == qLandList.empty())
{
int iCurX = qLandList.front().first;
int iCurY = qLandList.front().second;
qLandList.pop();
iMap[iCurX][iCurY] = rLandNumber; // 섬 번호 부여
int iJudgeEdgeCnt = 0; // 모퉁이를 찾기 위함
for (int i = 0; i < DIRECTION_COUNT; ++i)
{
int iTempX = iCurX + dx[i];
int iTempY = iCurY + dy[i];
if (0 > iTempX || iMapSize <= iTempX || 0 > iTempY || iMapSize <= iTempY) // 인덱스 범위 체크 Memory Corruption 방지
{
iJudgeEdgeCnt++;
continue;
}
if (0 > iMap[iTempX][iTempY]) // 방문이 가능하고, 섬인경우에만 후보리스트에 적재
{
qLandList.push(make_pair(iTempX, iTempY));
}
if (0 != iMap[iTempX][iTempY])
{
iJudgeEdgeCnt++;
}
}
if (DIRECTION_COUNT != iJudgeEdgeCnt)
{
CheckDuplicateValue(iCurX, iCurY);
}
}
}
/************************************************
@함수명 : CalculateShortestPath
@기능 : 가장 작은 거리를 찾는 함수
@입력값 :
@출력값 : int - 가장 작은 거리 값
@비고 :
*************************************************/
int CalculateShortestPath()
{
int iEdgeCount = static_cast<int>(vEdgeList.size());
int iAnswer = MAX_VERTEX_COUNT;
for (int iEIndex = 0; iEIndex < iEdgeCount - 1; ++iEIndex)
{
int curX = vEdgeList[iEIndex].first;
int curY = vEdgeList[iEIndex].second;
for (int iSubEIndex = iEIndex + 1; iSubEIndex < iEdgeCount; ++iSubEIndex)
{
int comX = vEdgeList[iSubEIndex].first;
int comY = vEdgeList[iSubEIndex].second;
if (iMap[curX][curY] != iMap[comX][comY]) // 서로 다른 섬이라는 것을 의미
{
int distance = abs(curX - comX) + abs(curY - comY) - 1;
if (iAnswer > distance)
{
iAnswer = distance;
}
}
}
}
return iAnswer;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> iMapSize;
Input();
vEdgeList.reserve(25);
int iLandNum = 1; // 1부터 시작하는 이유는 섬의 구분자가 1이기 때문에 0부터 시작은 할 수가 없음
for (int iRow = 0; iRow < iMapSize; ++iRow)
{
for (int iCol = 0; iCol < iMapSize; ++iCol)
{
if (0 > iMap[iRow][iCol])
{
MakeLand_Number(iRow, iCol, iLandNum);
iLandNum++;
}
}
}
cout << CalculateShortestPath();
return 0;
}