24.05.29 14:04 작성
·
95
·
수정됨
0
안녕하세요 선생님. 해당 질문에 대해서 저는 for 반복문을 이용해서 풀었습니다.
선생님께서는 while문을 이용해서 푸셨는데, 이러한 상황에서 시간복잡도 , 코드 효율성 등이 for문을 사용하는게 좋은지 while문이 좋은지 궁금합니다.
또한, while문의 시간 복잡도를 구하는게 조금 헷갈리는데 간단하게라고 설명 해주시면 감사하겠습니다.
#include <bits/stdc++.h>
using namespace std;
const int MAX_K = 2500;
const int MAX_M = 50;
const int MAX_N = 50;
const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1, 0, -1};
int T, N, M, K;
bool IsMovable(int dirY, int dirX, int visited[MAX_N][MAX_M], int Map[MAX_N][MAX_M])
{
if (dirY >= N || dirX >= M || dirY < 0 || dirX < 0)
return false;
if (visited[dirY][dirX] != 0) // 방문한 적 있으면
return false;
if (Map[dirY][dirX] != 1) // 갈 수 없는 곳이면
return false;
return true;
}
void Go(int cy, int cx, int visited[MAX_N][MAX_M], int Map[MAX_N][MAX_M])
{
visited[cy][cx] = 1;
for (int i = 0; i < 4; i++)
{
int ny = cy + dy[i];
int nx = cx + dx[i];
if (IsMovable(ny, nx, visited, Map))
Go(ny, nx, visited, Map);
}
}
int main()
{
cin >> T;
for (int i = 0; i < T; i++)
{
int Map[MAX_N][MAX_M]{};
int visited[MAX_N][MAX_M]{};
int zoneCnt = 0;
cin >> M >> N >> K;
for (int j = 0; j < K; j++)
{
int diry = 0;
int dirx = 0;
cin >> diry >> dirx;
Map[diry][dirx] = 1;
}
for (int currY = 0; currY < N; currY++)
{
for (int currX = 0; currX < M; currX++)
{
if (IsMovable(currY, currX, visited, Map))
{
zoneCnt++;
Go(currY, currX, visited, Map);
}
}
}
cout << zoneCnt<< endl;
}
}
답변 1
0
2024. 05. 30. 07:20
안녕하세요 룰루님 ㅎㅎ
for (int i = 0; i < T; i++)
{
이부분을 while문이 아닌 for문으로 하셨다는거죠?
for문과 while문의 시간복잡도는 크게 상이하지 않습니다. for문도 괜찮고 while문도 괜찮습니다.
또한, while문의 시간 복잡도를 구하는게 조금 헷갈리는데 간단하게라고 설명 해주시면 감사하겠습니다.
>>
while문이 얼마나 동작했나를 보시면 됩니다. 이 문제의 해설코드 같은 경우 while(T--)를 했기 때문에 while문의 시간복잡도는 O(T)가 됩니다.
다만, 이 코드를 제출했을 때 틀렸습니다가 나오는데 혹시 코드 잘못올리신게 아닌가요?
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.