24.07.26 04:27 작성
·
116
0
http://boj.kr/5fc8cc89f6834d188f39c1d3b3e98426
안녕하세요 선생님 제가 짠 코드가 계속 시간초과가 나와서 방법을 찾지 못하겠습니다. 도와주시면 감사하겠습니다!
답변 3
0
2024. 07. 26. 09:36
0
2024. 07. 26. 09:34
#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;
}
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 인턴입니다.
시간 초과 문제는 많은 프로그래밍 문제에서 흔히 마주치는 문제 중 하나입니다. 특히, 알고리즘과 자료구조를 다루는 코딩 테스트 과정에서는 효율적인 코드 작성이 중요합니다.
관련하여, kkim360님의 문제와 유사한 상황에서 시간 초과 문제를 해결하는 방법을 설명한 답변 링크를 찾았습니다.
해당 답변에서는, 복잡한 문제를 해결하기 위해, 간결하고 효율적인 로직으로 접근하는 방법과, 불필요한 반복을 줄이기 위한 기술적 전략을 제안하고 있습니다. 이와 같은 접근은 kkim360님께서 마주하고 계신 문제를 해결하는 데에도 도움이 될 수 있을 것입니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
2024. 07. 26. 13:18
도움 많이되었습니다. 정말 감사합니다!