백준 21736번 [헌내기는 친구가 필요해](C++) -yes6686- 티스토리

백준 문제 풀이: 21736 [헌내기는 친구가 필요해]

---

문제 링크: https://www.acmicpc.net/problem/21736

문제 설명:

n×m 크기의 캠퍼스에서 헌내기 위치 'I'에서 시작하여 친구 'P'의 수를 탐색하는 문제입니다. 장애물 'X'을 지나갈 수 없으며, 캠퍼스 밖으로 나갈 수 없습니다. 친구를 모두 탐색했을 때 친구의 수를 출력합니다. 만약 친구가 없다면 "TT"를 출력합니다.

입력:

• 첫째 줄에 캠퍼스의 크기 n, m이 주어집니다. (1 ≤ n, m ≤ 600)
• 다음 n개의 줄에는 n×m 크기의 캠퍼스 정보가 주어집니다.

출력:

• 만약 친구를 발견했다면 친구의 수를 출력합니다.
• 친구를 찾지 못했다면 "TT"를 출력합니다.

예시:

입력:
3 3
IOX
XPX
XXX

출력:
1

---

문제 해결 코드

#include <iostream>
using namespace std;

char arr[601][601]; // 캠퍼스 배열
bool visited[601][601]; // 방문 여부
int n, m, cnt = 0;

// DFS 탐색
void dfs(int x, int y) {
    if (x < 0 || y < 0 || x >= n || y >= m) return; // 캠퍼스 범위를 벗어난 경우
    if (visited[x][y] || arr[x][y] == 'X') return; // 이미 방문했거나 장애물인 경우

    visited[x][y] = true;

    if (arr[x][y] == 'P') cnt++; // 친구 발견 시 카운트 증가

    // 상하좌우 탐색
    dfs(x + 1, y);
    dfs(x - 1, y);
    dfs(x, y + 1);
    dfs(x, y - 1);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

    int startX = 0, startY = 0;

    // 캠퍼스 입력 및 헌내기 위치 저장
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 'I') {
                startX = i;
                startY = j;
            }
        }
    }

    // DFS 탐색 시작
    dfs(startX, startY);

    // 결과 출력
    if (cnt == 0) {
        cout << "TT" << '\n';
    } else {
        cout << cnt << '\n';
    }

    return 0;
}

---

코드 설명

이 코드는 DFS(깊이 우선 탐색)를 사용하여 캠퍼스를 탐색하고 친구 'P'의 수를 세는 문제를 해결합니다. 주요 로직과 알고리즘은 다음과 같습니다:

• 핵심 알고리즘: DFS를 사용하여 헌내기 'I'로부터 연결된 모든 경로를 탐색합니다.
• 구현 세부사항:
  • 배열 visited를 사용하여 중복 방문을 방지합니다.
  • cnt: 친구 'P'를 발견한 개수를 저장합니다.
  • 캠퍼스 범위를 벗어나거나 장애물 'X'를 만나면 탐색을 종료합니다.
• 시간 복잡도 분석:
  • DFS는 최대 캠퍼스의 모든 칸(600×600)을 탐색하므로 O(n × m)의 시간 복잡도를 가집니다.

---

결과

코드는 캠퍼스를 효율적으로 탐색하여 친구 'P'를 찾고, 발견된 친구의 수를 출력합니다. 친구가 없는 경우에는 "TT"를 출력합니다. 입력 크기 제한 내에서 효율적으로 작동합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!