인프런 커뮤니티 질문&답변
작성한 질문수
맵과 방향벡터 퀴즈 질문있습니다
작성
·
295
·
수정됨
0
안녕하십니까 큰돌님
Q. 3 * 3 맵을 입력받아야 함. 이 맵은 1과 0으로 이루어져있고 {0, 0}은 무조건 1임을 보장한다. {0, 0}부터 4방향을 기준으로 한칸씩 탐색해나가며 방문한 정점은 다시 방문하지 않으며 방문하는 좌표를 출력하는 코드. 0은 갈 수 없는 지역. 1은 갈 수 있는 지역을 구현하시오.
1. 문제의 뜻이 {0, 0}을 기준으로 4방향으로 탐색하는데 다 0이면 그 다음 칸인 {0, 1}로 이동하는데 0이니까 그 다음 칸인 {0, 2}를 기준으로 4방향을 탐색하는데 밑에 1이 있으니까 {1, 2}를 기준으로 또 4방향으로 탐색하고~, 이렇게 하라는 뜻이 아닌 거죠 ??
저는
0 : 0
1 : 0
0 : 2
1 : 2
2 : 2
2 : 1
이렇게 출력되게 해야하는 줄 알았는데 위 문제의 답 코드를 실행시키면
0 : 0
1 : 0
이렇게 나와서 제가 이해력이 안 좋아서 질문드립니다 ㅎ
dfs까지 추가로 강의를 들었는데 위 퀴즈의 go 함수 로직이 사실 dfs 로직인 건가요 ??
종화는 방구쟁이야! 문제의 dfs 로직과 위 퀴즈의 go 함수 로직과 거의 유사해보여서요 )
트리 순회의 조건문 visited[here] == 0 안의 로직에서 중위 순회에서만 else-if 문을 사용하는데 http://boj.kr/9ed45ee550c0492081f5cbd187a7c71d 이런식으로 전위, 후위에서도 자식 노드가 한 개 아니면 두 개 둘 중에 하나니까 두 번 if문 볼 필요없게 else-if문 사용해도 되는거죠 ??
답변 3
0
void postOrder(int here){
if (visited[here] == 0) {
if (adj[here].size() == 1) postOrder(adj[here][0]);
else if (adj[here].size() == 2) { postOrder(adj[here][0]); postOrder(adj[here][1]); }
visited[here] = 1;
cout << here << " ";
}
}
void postOrder(int here) {
if(visited[here] == 0) {
if(adj[here].size() == 1) postOrder(adj[here][0]);
if(adj[here].size() == 2) { postOrder(adj[here][0]); postOrder(adj[here][1]); }
visited[here] = 1; cout << here << ' ';
}
}
3번만 재질문하면 위에가 제 코드인데 밑에가 강사님 코드인데 if (visited[here] == 0) 안에서 저는 if else-if로 사용했는데 저렇게 하면 안된다는 뜻인가용 ??
0
안녕하세요 대기업님 ㅎㅎ
1. 문제의 뜻이 {0, 0}을 기준으로 4방향으로 탐색하는데 다 0이면 그 다음 칸인 {0, 1}로 이동하는데 0이니까 그 다음 칸인 {0, 2}를 기준으로 4방향을 탐색하는데 밑에 1이 있으니까 {1, 2}를 기준으로 또 4방향으로 탐색하고~, 이렇게 하라는 뜻이 아닌 거죠 ??
>> 음.. 계속해서 4방향으로 탐색하는 건 맞는데 그 예제 자체가
일단 이 맵을 기반으로 탐색합니다.
1 0 1
1 0 1
0 1 1그렇기 때문에 2번밖에 찍히지 않게 됩니다.
dfs까지 추가로 강의를 들었는데 위 퀴즈의 go 함수 로직이 사실 dfs 로직인 건가요 ??
>> 네 맞습니다.
전위, 후위에서도 자식 노드가 한 개 아니면 두 개 둘 중에 하나니까 두 번 if문 볼 필요없게 else-if문 사용해도 되는거죠 ??
>> 아닙니다. 자식노드가 한개 아니면 2개 둘 중에 하나일 수가 있고 없을 수도 있습니다. 로직상 중위순회는
inOrder(adj[here][0]);
visited[here] = 1;
cout << here << ' ';
inOrder(adj[here][1]);
앞의 코드처럼 중간에 넣어야 하기 때문에 if문이 더 있는 것입니다.
감사합니다.
0
안녕하세요, 인프런 AI 인턴이에요.
주어진 문제에서는 3x3 크기의 맵을 탐색하면서 1인 지역을 방문하는 코드를 구현하는 것 같습니다. 이때, {0, 0}부터 시작해서 4방향을 탐색하며 방문한 지점은 다시 방문하지 않도록 구현해야 합니다.
문제에서 언급한 방식으로 코드를 작성하면 됩니다. {0, 0}부터 시작해서 상하좌우로 움직이면서 1인 지역을 탐색하고, 해당 좌표를 출력하면 됩니다.
주어진 코드에서는 현재 위치를 나타내는 좌표(x, y)를 {0, 0}으로 초기화하고, 현재 위치가 1인 경우에만 해당 좌표를 출력하고 다음 좌표로 이동하는 방식으로 구현되어 있습니다. 따라서, 이 코드는 DFS 로직을 구현한 것입니다.
만약 위 코드가 정상적으로 동작하지 않는다면, 코드를 분석해 보고 문제의 조건에 맞게끔 수정을 해야 할 것입니다. 추가적으로, DFS에 대한 개념을 다시 한번 복습해보시는 것도 좋을 것 같아요.
문제에 대한 질문이 있으시다면 언제든지 물어보세요!