[Python][C++] 21736번 헌내기는 친구가 필요해

문제

https://www.acmicpc.net/problem/21736

 

 

 

 

코드

1. Python

import sys
from collections import deque

input = sys.stdin.readline  # 빠른 입력을 위해 sys.stdin.readline 사용

# BFS(너비 우선 탐색) 함수 정의
def bfs(x, y):
    # 상하좌우 탐색을 위한 방향 벡터
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    # 방문 여부를 기록하는 2차원 리스트
    visited = [[0] * m for _ in range(n)]
    cnt = 0  # 만날 수 있는 사람의 수를 저장하는 변수

    # BFS를 위한 큐 초기화 및 시작 위치 삽입
    q = deque()
    q.append([x, y])
    visited[x][y] = 1  # 시작 위치 방문 처리

    # 큐가 빌 때까지 탐색
    while q:
        x, y = q.popleft()
        # 상하좌우 네 방향 탐색
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            # 보드의 범위를 벗어나지 않고, 방문하지 않은 곳이고, 벽('X')이 아닌 경우
            if 0 <= nx < n and 0 <= ny < m:
                if board[nx][ny] != 'X' and not visited[nx][ny]:
                    visited[nx][ny] = 1  # 방문 처리
                    q.append([nx, ny])  # 다음 위치 큐에 삽입

                    # 사람이 있는 위치('P')일 경우 카운트 증가
                    if board[nx][ny] == 'P':
                        cnt += 1

    return cnt  # 만날 수 있는 사람의 수 반환

# 보드의 크기(n: 행, m: 열) 입력
n, m = map(int, input().split())
board = [input().rstrip() for _ in range(n)]  # 보드 상태 입력

# 시작 위치('I')를 찾음
for i in range(n):
    for j in range(m):
        if board[i][j] == 'I':
            start_x, start_y = i, j  # 시작 위치 기록
            break

# BFS 수행하여 만날 수 있는 사람의 수 계산
ans = bfs(start_x, start_y)

# 결과 출력: 만날 수 있는 사람이 없으면 "TT" 출력, 그렇지 않으면 만난 사람 수 출력
print(ans if ans else "TT")

 

2. C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// BFS 함수: 시작 위치 (x, y)에서 보드를 탐색하며 'P'의 개수를 센다
int bfs(int x, int y, int n, int m, const vector<string> board) {
    int dx[] = { -1, 1, 0, 0 };  // 상하좌우 이동을 위한 배열
    int dy[] = { 0, 0, -1, 1 };  // 상하좌우 이동을 위한 배열
    
    queue<pair<int, int>> q;  // BFS를 위한 큐
    vector<vector<int>> visited(n, vector<int>(m));  // 방문 여부를 체크할 배열
    int cnt = 0;  // 'P'의 개수를 세는 변수

    q.push(make_pair(x, y));  // 시작 위치를 큐에 넣음
    visited[x][y] = 1;  // 시작 위치 방문 처리
    
    while (!q.empty()) {
        x = q.front().first;  // 현재 위치의 x 좌표
        y = q.front().second;  // 현재 위치의 y 좌표
        q.pop();

        if (board[x][y] == 'P')  // 현재 위치에 'P'가 있으면 카운트 증가
            cnt++;

        // 상하좌우로 이동
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];  // 새로운 x 좌표
            int ny = y + dy[i];  // 새로운 y 좌표

            // 보드의 범위를 벗어나면 무시
            if (0 > nx || nx >= n || 0 > ny || ny >= m)
                continue;

            // 'X'가 아니고 방문하지 않은 위치만 탐색
            if (board[nx][ny] != 'X' && !visited[nx][ny]) {
                q.push(make_pair(nx, ny));  // 새로운 위치를 큐에 추가
                visited[nx][ny] = 1;  // 방문 처리
            }
        }
    }

    return cnt;  // 'P'의 개수 반환
}

int main() {
    int n, m;
    cin >> n >> m;  // 보드의 크기 n x m 입력

    vector<string> board(n);  // 보드를 저장할 벡터

    int sx = -1, sy = -1;  // 'I'의 위치를 저장할 변수

    // 보드 입력
    for (int i = 0; i < n; i++) {
        cin >> board[i];  // 각 행의 문자열 입력

        // 'I'의 위치 찾기
        for (int j = 0; j < m; j++) {
            if (board[i][j] == 'I') {
                sx = i;  // 시작 위치의 x 좌표
                sy = j;  // 시작 위치의 y 좌표
            }
        }
    }

    // BFS를 수행하여 'P'의 개수 반환
    int ret = bfs(sx, sy, n, m, board);

    // 결과 출력
    if (ret)
        cout << ret;
    else
        cout << "TT";  // 'P'를 찾지 못한 경우 "TT" 출력

    return 0;
}

 

 

풀이

 

1. 그래프 탐색:
   • 캠퍼스를 2차원 격자로 보고, 도연이가 이동할 수 있는 모든 영역을 탐색해야 한다.
   • '도연'이의 위치에서 시작하여 상하좌우로 이동하며 'O'로 표시된 빈 공간을 탐색한다.
   • 이동하는 동안 만나는 친구('P')의 수를 세어 나간다.
2. 탐색 조건:
   • 도연이는 빈 공간('O')과 친구가 있는 칸('P')만 이동할 수 있다.
   • 벽('#')은 이동이 불가능하며, 이를 통해 탐색을 제한한다.
   • 탐색을 시작하기 위해 먼저 'I'의 위치(도연이의 위치)를 찾는다.
3. BFS 사용:
   • 'I'의 위치에서 BFS나 DFS를 시작하여, 방문할 수 있는 모든 칸을 탐색한다.
   • 탐색하면서 만나는 친구의 수를 카운트한다.
   • 이미 방문한 칸은 다시 방문하지 않도록 표시하여 중복 탐색을 방지한다.
4. 경계 조건:
   • 격자 밖으로 나가지 않도록 경계를 검사한다.
   • 상하좌우로만 이동할 수 있으므로, 각 위치에서 네 방향(위, 아래, 왼쪽, 오른쪽)으로 이동을 시도한다.
5. 결과 처리:
   • BFS 또는 DFS가 종료된 후, 만난 친구의 수를 출력한다.
   • 만약 친구를 만나지 못하면 TT를 출력한다.