🤍 전 강의 25% 할인 중 🤍

2024년 상반기를 돌아보고 하반기에도 함께 성장해요!
인프런이 준비한 25% 할인 받으러 가기 >>

  • 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

2-B. 유기농 배추 질문있습니다.

24.05.29 14:04 작성 24.05.29 14:04 수정 조회수 54

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

안녕하세요 룰루님 ㅎㅎ

    for (int i = 0; i < T; i++)
    {

이부분을 while문이 아닌 for문으로 하셨다는거죠?

for문과 while문의 시간복잡도는 크게 상이하지 않습니다. for문도 괜찮고 while문도 괜찮습니다.

 

또한, while문의 시간 복잡도를 구하는게 조금 헷갈리는데 간단하게라고 설명 해주시면 감사하겠습니다.

>>

while문이 얼마나 동작했나를 보시면 됩니다. 이 문제의 해설코드 같은 경우 while(T--)를 했기 때문에 while문의 시간복잡도는 O(T)가 됩니다.

 

 

다만, 이 코드를 제출했을 때 틀렸습니다가 나오는데 혹시 코드 잘못올리신게 아닌가요?



또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.


 

채널톡 아이콘