인프런 커뮤니티 질문&답변

kkim360님의 프로필 이미지

작성한 질문수

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

3-K와 문제의 단순화

3 - k 시간초과

24.07.26 04:27 작성

·

143

0

http://boj.kr/5fc8cc89f6834d188f39c1d3b3e98426

안녕하세요 선생님 제가 짠 코드가 계속 시간초과가 나와서 방법을 찾지 못하겠습니다. 도와주시면 감사하겠습니다!

답변 3

0

큰돌님의 프로필 이미지
큰돌
지식공유자

2024. 07. 26. 09:36

후... 이거 코드포맷 올리는거 버그 있네요.. ㅂㄷㅂㄷ ... http://boj.kr/3e69827dd5cb42d5a05c2911fe49d11a제가 kkim님 코드 다듬으면서 + 주석 단 코드입니다. 이거 참고해주세요~ ㅎㅎ

0

큰돌님의 프로필 이미지
큰돌
지식공유자

2024. 07. 26. 09:34

안녕하세요 kkim님 ㅎㅎ너무나도 잘 짜셨네요 ㅎㅎkkim님 코드 다듬으면서 + 주석 달았습니다. 코드리뷰 참고해주세요~#include <bits/stdc++.h> using namespace std; int y, x; int n, m, swan_y, swan_x, visited[1504][1504], visited_swan[1504][1504]; int dy[] = {-1, 0, 1, 0}; int dx[] = {0, 1, 0, -1}; char c[1504][1504]; queue<pair<int, int>> q; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 0; i < n; i++) { string s; cin >> s; for (int j = 0; j < m; j++) { c[i][j] = s[j]; // 이렇게 해서 중복되는 부분 다 처리해요~ if (c[i][j] == '.' || c[i][j] == 'L') { q.push({i, j}); visited[i][j] = 1; } if (c[i][j] == 'L') { swan_y = i; swan_x = j; } } } queue<pair<int, int>> swan; queue<pair<int, int>> swan_temp; visited_swan[swan_y][swan_x] = 1; swan.push({swan_y, swan_x}); int cnt = 0; while (true) { while (!swan.empty()) { tie(y, x) = swan.front(); swan.pop(); for (int i = 0; i < 4; i++) { int ny = y + dy[i]; int nx = x + dx[i]; if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue; if (visited_swan[ny][nx]) continue; // 기저사례부터 하는 습관 if (c[ny][nx] == 'L') { cout << cnt << '\n'; return 0; } // 중복되는 부분 처리 if (visited[ny][nx]) { swan.push({ny, nx}); } else { swan_temp.push({ny, nx}); } visited_swan[ny][nx] = 1; } } swan = swan_temp; // swap_temp - clear 해주어야 해요~ while (!swan_temp.empty()) swan_temp.pop(); cnt++; int q_size = q.size(); while (q_size--) { tie (y, x) = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int ny = y + dy[i]; int nx = x + dx[i]; if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue; if (visited[ny][nx]) continue; // .으로 바꿔줘야 합니다. if (c[ny][nx] == 'X') { c[ny][nx] = '.'; q.push({ny, nx}); } visited[ny][nx] = 1; } } } return 0; }
kkim360님의 프로필 이미지
kkim360
질문자

2024. 07. 26. 13:18

도움 많이되었습니다. 정말 감사합니다!

kkim360님의 프로필 이미지
kkim360
질문자

2024. 07. 28. 06:33

선생님 79번줄에

if (visited[ny][nx]) continue;

// .으로 바꿔줘야 합니다.

if (c[ny][nx] == 'X') {

c[ny][nx] = '.';

q.push({ny, nx});

}

visited[ny][nx] = 1;

여기서 c[ny][nx] 를 '.'으로 바꾸어야 하는 이유가 뭔가요?

제 생각에서는 '.'으로 바꾸지 않아도 ny nx 좌표는 바로 밑에서 visited 처리가 되어서

다음번 순회때 if (visited[ny][nx]) continue; 부분에서 걸러져서 상관 없을것이라 생각했습니다

백조는 '.'를 따라 움직이는것이 아니라 visited[][]가 0인 부분을 따라서 움직이는 알고리즘이라 생각되어서 c[][]값 갱신의 이유를 모르겠습니다!

큰돌님의 프로필 이미지
큰돌
지식공유자

2024. 07. 29. 15:25

안녕하세요 kkim님ㅎㅎ

                if (c[ny][nx] == 'X') { 
                    q.push({ny, nx});
                }

네 맞습니다. c 안바꿔도 됩니다. ㅎㅎ 제가 착각했어요 혼란을 드려 죄송합니다. ㅠ

 

감사합니다.

0

인프런 AI 인턴님의 프로필 이미지

2024. 07. 26. 04:31

안녕하세요, 인프런 AI 인턴입니다.

시간 초과 문제는 많은 프로그래밍 문제에서 흔히 마주치는 문제 중 하나입니다. 특히, 알고리즘과 자료구조를 다루는 코딩 테스트 과정에서는 효율적인 코드 작성이 중요합니다.

관련하여, kkim360님의 문제와 유사한 상황에서 시간 초과 문제를 해결하는 방법을 설명한 답변 링크를 찾았습니다.

  • 시간 초과 문제를 해결하는 방법에 대한 설명이 담긴 질문 “시간초과 문제 해결법“에서는 시간초과가 나는 주된 이유와 개선 방안에 대해 설명하고 있습니다. 여기서는 특히 효율적인 자료구조의 선택, 반복문의 최적화, 불필요한 계산 최소화 등 시간 복잡도를 줄이는 다양한 방법을 제시합니다.

해당 답변에서는, 복잡한 문제를 해결하기 위해, 간결하고 효율적인 로직으로 접근하는 방법과, 불필요한 반복을 줄이기 위한 기술적 전략을 제안하고 있습니다. 이와 같은 접근은 kkim360님께서 마주하고 계신 문제를 해결하는 데에도 도움이 될 수 있을 것입니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

kkim360님의 프로필 이미지

작성한 질문수

질문하기