데옹의 블로그

이 문제는 보자마자 걍 DFS로 풀어야겠다는 생각을 했습니다. 바로 풀어봅시다. 처음에 한 생각은 들어가서 집을 철거해버리고 철거한 만큼의 수를 세어 리스트에 저장하면 되겠다 싶었습니다. 철거해버리면 다음에 그 곳을 셀 필요가 없어지니까요 ㅋㅋ ^_^ 위 사진이 정말 적절하다고 생각해서 첨부해봤어요... 철거 해버리면 다시 dfs로 탐색할 때 탐색 못 하니까요. 분명 있었는데... 사라졌으니까 갯수를 셀 수가 없죠... (visited를 사용하지 않아도 되는 이유가 됩니다) 암튼 이 단순한 생각을 그냥 코드로 끄적여봤습니다. from collections import deque import sys input = sys.stdin.readline n = int(input()) def dfs(x,y): gl..

아시겠지만, 간단하게 1번 노드와 연결된 노드의 갯수만 세면 되는 문제입니다. 구구절절 잡다한 설명은 치우고 바로 시작합시다. 우선 생각해야 할 것들이 뭐가 있을까요? 바로 1번과 직접적으로든 간접적으로든 연결이 되어있지 않다면 그건 확인할 필요가 없다는 걸 생각해야죠! 그리고, 1번과 관계가 있는 노드는 모두 카운트 해야합니다. 근데 또 생각해보면 쉽더라고요. 왜냐면 그냥 1번부터 시작했으니까 visited 된 (방문 처리 된) 것들을 세보면 되지 않을까요? 생각은 다 했으니까.. 어떻게 구현을 해볼까 생각을 해봐야죠. 근데 dfs를 할 때, graph라는 list를 만들어서 했었습니다. 그래서 연관된 것들을 계속 찾아갔죠. 그러니까 dfs가 완성이 되었고요.. 그러면 저희는 그냥 graph[1]번을 ..

DFS와 BFS를 공부 중인데, 이론적으로 이해하는 건 되지만 계속 헷갈려서 코드만 정리하면서 써보려구요. 갑니다.. 더 친절한 설명을 원하면 다른 블로그를 참고해주세요! from collections import deque from sys import stdin input = stdin.readline # 입력을 받는 곳입니다. n,m,v = map(int, input().split()) # 1. 그래프 초기화 ## 인덱스를 1부터 시작하기 위해서 n+1 을 해줍니다. ## 일반적으로 그래프의 노드 번호는 1부터 시작하는 경우가 많습니다. ## n은 실제 노드의 개수이고, 노드의 번호는 1부터 n까지이니 리스트의 크기를 n+1로 설정하여 ## 인덱스 1부터 n까지 사용할 수 있도록 초기화를 한 것입니다..