본문 바로가기 메뉴 바로가기

je_record

프로필사진
  • 글쓰기
  • 관리
  • 태그
  • 방명록
  • RSS

je_record

검색하기 폼
  • 분류 전체보기 (128)
    • 회고 (3)
    • 안드로이드[Kotlin] (7)
    • 알고리즘 (53)
    • CS (42)
      • 컴퓨터네트워크 (26)
      • 인터넷DB응용 (9)
      • 운영체제 (7)
    • 백엔드 (23)
      • Java (3)
      • 데이터베이스 (3)
      • SpringBoot (11)
  • 방명록

너비우선탐색 (3)
[백준 18352번/c++] 특정 거리의 도시 찾기

문제 특정 도시에서 출발하여 도달할 수 있는 모든 도시 중에서 특정 최단 거리를 가지는 도시 번호를 출력한다. https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 조건 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재 모든 도로의 거리는 1 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력 출발 도시 X에..

알고리즘 2023. 2. 13. 02:00
[프로그래머스/c++] 게임 맵 최단거리

문제 접근 캐릭터가 적 팀의 진영까지 가는 가장 빠른 길을 찾는 것으로, 최단 경로를 찾는 문제이다. 최단 경로를 찾는 문제의 경우 제일 먼저 BFS가 떠오른다! DFS의 경우 재귀함수를 호출하여 스택을 사용하므로 구조상 모든 경로를 다 탐색해보아야 하므로 BFS에 비해 시간이 오래 걸린다. BFS를 이용하여 최단거리를 구한다! 성공 코드 각각의 위치를 구조체 Loc를 통해 구현한다. 큐에 시작 위치인 (0, 0)을 넣는다. 큐가 비어있지 않은 동안 다음을 반복한다. 큐에 들어있는 원소를 하나 pop하여 pop한 원소의 위치에서 상, 하, 좌, 우를 탐색하며 게임 맵 크기의 범위에 들어가고 방문하지 않은 위치라면 큐에 해당 위치를 넣는다. 해당 위치의 distance를 pop한 원소의 위치까지의 dist..

알고리즘 2023. 1. 15. 20:19
[백준 2178번/c++] 미로 탐색(DFS 시간초과와 BFS)

알고리즘 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 DFS: 시간 초과 DFS를 이용하여 최단거리를 찾고자 하는 경우 완전 탐색 후 가장 작은 값을 선택하여야 하므로 경로가 많아질 수 있고 이렇게 되면 시간 복잡도가 커진다. #include #include #include using namespace std; int map[101][101], ch[101][101], n, m; int dx[4]={1, 0, -1, 0}; int dy[4]={0, 1, 0, -1}; int cnt=1, minn=2147000000; void DFS(int x, int y){ int xx, yy, i; if(x==n && y == m){ if(cnt

알고리즘 2022. 2. 9. 15:34
이전 1 다음
이전 다음

Blog is powered by Tistory / Designed by Tistory

티스토리툴바