특정 거리의 도시 찾기 (백준18352실버2)단방향그래프 BFS

• 링크 : https://www.acmicpc.net/problem/18352

메모

1부터 n개의 도시
m개의 단방향 edges (가중치 모두 1)

• 마지막 입력 : 출발 노드번호

• 세 번째 입력 : k

• 특정 도시 x에서 갈 수 있는 도시 중

  • 최단거리가 딱 k인 도시 번호를 모두 출력

• 만약 k가 하나도 없으면 -1출력

알고리즘 및 방법

bfs(시작노드번호)를 사용하는데
방향그래프니까, graph는 인접리스트를 사용해야겟구만

visit 리스트는 방문여부와 경로를 저장해야함

• 원본그래프는 링크드리스트 형태이므로!

bfs():
    링크드리스트를 타고가면서
    방문하지 않은 노드(-1)를 방문대상으로 append & 이전값에+1

    만약 k가 visit에 없으면 print(-1) return
    
    for i in 결과:
        if i == k:
            print(i) 전부 출력

test case 2

n, m, k, x = 4,3, 2, 1
graph = [[], [2, 3, 4], [], [], []]

test case 3

n, m, k, x = 4,4,1,1
graph = [[], [2, 3], [3, 4], [], []]

---

솔루션 코드 - 내가 푼

• python

from collections import deque
import sys
input = sys.stdin.readline

# input data
n, m, k, x = map(int, input().split())
# 인접 리스트 생성!
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)                  # (중요) 방향그래프이므로 이렇게만 추가해야한다

visit = [-1]*(n+1)                      # (중요) 갈 수 없는 노드는 -1이 된다!

def bfs(x):
    que = deque()
    que.append(x)
    visit[x] += 1
    
    while que:
        x = que.popleft()
        for nx in graph[x]:
            if visit[nx] == -1:        # 연결된 노드 중 방문하지 않은 노드만
                que.append(nx)
                visit[nx] = visit[x] + 1

    if k not in visit:
        print(-1)
        return
    
    for i in range(1, n+1):
        if visit[i] == k:
            print(i)

bfs(x)

• visit 그래프 결과물
  

• cpp (알아둘점 중요)

  • 2차원 배열 vector 선언 방법
  • 1차원 vector 초기화 방법
  • cpp 큐 사용법
  • cpp 인접리스트

#include <bits/stdc++.h>
using namespace std;

int n, m, k, x;
vector<int> graph[300001];        // (중요) 2차원 배열은 이렇게!
vector<int> visiting(300001, -1);    // (중요) 모든 도시에 대한 최단 거리 -> 초기화 방법
bool flag = false;

void bfs(int x) {
	// (중요) cpp에선 큐를 queue라이프러리로 사용 (사용법은 vector와 동일)
	queue<int> que;
	que.push(x);
	visiting[x]++;

	while (!que.empty()) {
		//int a = que.pop();      // (매우 중요) 이게 불가하다!
		int cur = que.front();    // = .popleft()
		que.pop();

		for (int i = 0; i < graph[cur].size(); i++) {
			int nx = graph[cur][i];     // (매우 중요) 인접리스트 노드 이렇게 가져와야 함!!

			if (visiting[nx] == -1) {
				que.push(nx);
				visiting[nx] = visiting[cur] + 1;
			}
		}
	}

	// flag를 사용해서, 브루트포스 검색 => 하나라도 있으면 출력, 없으면 -1을 출력해야함
	for (int i = 1; i <= n; i++) {
		if (visiting[i] == k) {
			cout << i << endl;
			flag = true;
		}
	}
	if (flag == false) {
		cout << -1 << endl;
	}
}

int main(void) {
	cin >> n >> m >> k >> x;

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);         // 위와 같이 생성할 경우 이렇게 가능!
	}

	bfs(x);
	return 0;                          // 백준 리턴 0없으면 컴파일에러임(main 함수선언도 int넣어야)
}

• 확실히 파이썬보다 빠른걸 볼 수 있음!
  

---

솔루션 코드 - 나동빈

• 링크 : https://github.com/ndb796/python-for-coding-test/blob/master/13/1.py

from collections import deque

# 도시의 개수, 도로의 개수, 거리 정보, 출발 도시 번호
n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n + 1)]

# 모든 도로 정보 입력 받기
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)

# 모든 도시에 대한 최단 거리 초기화
distance = [-1] * (n + 1)
distance[x] = 0 # 출발 도시까지의 거리는 0으로 설정

# 너비 우선 탐색(BFS) 수행
q = deque([x])
while q:
    now = q.popleft()
    # 현재 도시에서 이동할 수 있는 모든 도시를 확인
    for next_node in graph[now]:
        # 아직 방문하지 않은 도시라면
        if distance[next_node] == -1:
            # 최단 거리 갱신
            distance[next_node] = distance[now] + 1
            q.append(next_node)

# 최단 거리가 K인 모든 도시의 번호를 오름차순으로 출력
check = False
for i in range(1, n + 1):
    if distance[i] == k:
        print(i)
        check = True

# 만약 최단 거리가 K인 도시가 없다면, -1 출력
if check == False:
    print(-1)