[백준] 11403번 경로 찾기

2025. 3. 31. 21:38·백준 문제/그래프

문제: 11403번: 경로 찾기

basic-algo-lecture/workbook/0x18.md at master · encrypted-def/basic-algo-lecture

 

basic-algo-lecture/workbook/0x18.md at master · encrypted-def/basic-algo-lecture

바킹독의 실전 알고리즘 강의 자료. Contribute to encrypted-def/basic-algo-lecture development by creating an account on GitHub.

github.com

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n;
vector<vector<int>> graph(101, vector<int>(101));
vector<vector<int>> answer(101, vector<int>(101));

void BFS(int start) {
    vector<bool> visit(101, false); // 방문 배열을 매번 초기화
    queue<int> nexts;
    nexts.push(start);

    while (!nexts.empty()) {
        int cur = nexts.front();
        nexts.pop();

        for (int i = 0; i < n; i++) { // 0-based index 사용
            if (graph[cur][i] == 1 && !visit[i]) {
                visit[i] = true;
                answer[start][i] = 1; // start에서 i까지 도달 가능
                nexts.push(i);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    for (int i = 0; i < n; i++) { // 0-based index
        for (int j = 0; j < n; j++) {
            cin >> graph[i][j];
        }
    }

    // 모든 정점에서 BFS 실행
    for (int i = 0; i < n; i++) {
        BFS(i);
    }

    // 결과 출력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << answer[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}

 

기존 BFS 풀이에서 살짝 달라지는 점은 맨 처음 시작 노드를 nexts 에 넣을 때 방문처리를 바로 하지 않는 것이다.. ㄷㄷ 방문처리를 먼저 하고 while 돌리면 만약 시작 지점으로 돌아오는 길이 있을 때를 반영해주지 못해서 방문 처리를 하지 않는 것이었다.

 

이것만 생각해주면 나머지는 딱히 다를바가 없다. 외부에서 모든 정점을 시작지점으로 해서 BFS 를 돌려주면 된다. main 에서 BFS 돌리려고 할 때도 현재 시작 지점으로 주려고 하는 정점이 이미 방문한 곳인지 확인하지 않는다.

'백준 문제/그래프' 카테고리의 다른 글
  • [백준] 24446번 알고리즘 수업 - 너비 우선 탐색 3
  • [백준] 1707번 이분 그래프
  • [백준] 5567번 결혼식
  • [백준] 2606번 바이러스
dubu0721
dubu0721
dubu0721 님의 블로그 입니다.
  • dubu0721
    dubu0721 님의 블로그
    dubu0721
  • 전체
    오늘
    어제
    • 분류 전체보기 (348) N
      • 프로그래밍언어론 정리 (5)
      • 컴퓨터네트워크 정리 (5)
      • 알고리즘&자료구조 공부 (64)
        • it 취업을 위한 알고리즘 문제풀이 입문 강의 (60)
        • 학교 알고리즘 수업 (3)
        • 실전프로젝트I (0)
      • 백준 문제 (201) N
        • 이분탐색 (7)
        • 투포인트 (10)
        • 그래프 (11)
        • 그리디 (24)
        • DP (25)
        • BFS (18)
        • MST (7)
        • KMP (4)
        • Dijkstra (3)
        • Disjoints Set (4)
        • Bellman-Ford (2)
        • 시뮬레이션 (3)
        • 백트래킹 (15)
        • 위상정렬 (5)
        • 자료구조 (25)
        • 기하학 (1)
        • 정렬 (11)
        • 구현 (8)
        • 재귀 (8)
        • 수학 (8)
        • 트리 (1) N
      • 유니티 공부 (11)
        • 레트로의 유니티 게임 프로그래밍 에센스 (11)
        • 유니티 스터디 자료 (0)
        • C# 공부 (0)
      • 유니티 프로젝트 (48)
        • 케이크게임 (13)
        • 점토게임 (35)
      • 언리얼 공부 (10)
        • 이득우의 언리얼 프로그래밍 (10)
      • 진로 (1)
      • 논문 읽기 (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    언리얼
    레트로의 유니티 프로그래밍
    C#
    시뮬레이션
    그래프
    스택
    백트래킹
    이득우
    큐
    dp
    백준
    그리디
    투포인터
    맵
    유니티 공부 정리
    오블완
    유니티 프로젝트
    이벤트 트리거
    BFS
    골드메탈
    자료구조
    티스토리챌린지
    우선순위큐
    바킹독
    수학
    해시
    정렬
    유니티
    재귀
    이분탐색
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
dubu0721
[백준] 11403번 경로 찾기

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.