인프런 커뮤니티 질문&답변
작성한 질문수
3-L 코드가 왜 틀렸는지 모르겠습니다.
해결된 질문
작성
·
45
·
수정됨
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
아래 코드가 테스트 케이스를 다 통과하는데 왜 틀렸는지 모르겠어요..
#include <bits/stdc++.h>
using namespace std;
int ret, r, c, result;
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };
int visited[30][30];
char a[30][30];
int t[30];
void dfs(int sy, int sx) {
visited[sy][sx] = 1;
t[a[sy][sx]] = 1;
ret++;
result = max(result, ret);
for (int i = 0; i < 4; i++) {
int ny = sy + dy[i];
int nx = sx + dx[i];
if (ny < 0 || ny >= r || nx < 0 || nx >= c || visited[ny][nx]) continue;
if (t[a[ny][nx]]) continue;
dfs(ny, nx);
visited[ny][nx] = 0;
t[a[ny][nx]] = 0;
ret--;
}
}
int main() {
cin >> r >> c;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> a[i][j];
}
}
dfs(0, 0);
cout << result;
}답변 1
0
큰돌
지식공유자
안녕하세요 ㅎㅎ
원복 부분이 잘못되었습니다. 방문 해서 visited처리할거면 -> 방문하고 나서 나갈 때의 visited미처리 식으로 포맷팅을 맞춰줘야 합니다.
예를 들어 a라는 정점을 방문처리 -> 탐색 -> a정점 방문 미처리 이렇게 되어야 하는데 지금 코드가 a라는 정점 방문처리 -> 탐색 -> b, c, d 정점 방문 미처리
이렇게 되어있는 것이죠.
제가 한번 다듬어봤습니다. 참고부탁드립니다.
#include <bits/stdc++.h>
using namespace std;
int ret, r, c, result;
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };
int visited[30][30];
int t[26];
char a[30][30];
void dfs(int sy, int sx) {
visited[sy][sx] = 1;
t[a[sy][sx] - 'A'] = 1;
ret++;
result = max(result, ret);
for (int i = 0; i < 4; i++) {
int ny = sy + dy[i];
int nx = sx + dx[i];
if (ny < 0 || ny >= r || nx < 0 || nx >= c || visited[ny][nx]) continue;
if (t[a[ny][nx] - 'A']) continue;
dfs(ny, nx);
}
// 원복
visited[sy][sx] = 0;
t[a[sy][sx] - 'A'] = 0;
ret--;
}
int main() {
cin >> r >> c;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> a[i][j];
}
}
dfs(0, 0);
cout << result;
return 0;
}
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.