개발자로 취직하기의 DFS 강의 : inf.run/MqJT 파이썬 코드 : coding-grandpa.tistory.com/120 문제 보기 : www.acmicpc.net/problem/1012 00:00 문제 설명 04:30 정석 풀이 10:43 더 간결한 풀이 #유기농배추 #백준1012 #파이썬
네 최초에 배열을 선언할 때 MAX개를 만듭니다. 이때 MAX는 최댓값인 50에 10을 더해서 60개씩 만들어요~! 이론적으로는 (최댓값 + 2)개만 만들어도 충분한데, 그냥 습관이 되어 넉넉히 10개 추가해서 사용하고 있습니다 ㅎㅎ 그러면 여러모로 고려할 예외 케이스가 줄어들어서 코드도 간결해져요.
안녕하세요 개발자로 취직하기님 항상 영상 잘 보고 있습니다. 다름이 아니라 코드보고 궁금증이 생겨 댓글 남깁니다. 질문 - visited를 global로 할 필요가없을 것 같은데 하신 이유가 있나요?? - dfs 함수가 for문 안에 들어가기 때문에 동일 스콥이라 global로 할 필요없지 않을까요?? (global도 하지 않을 때 동일한 결과가 나오는 것 확임함) - 마찬가지로 graph 변수는 global로 하지 않았지만 dfs 함수에 잘 사용하고 있는 것을 확인할 수 있습니다. graph 변수는 global로 하지 않고 visited만 global로 하는 것이 의도된 것이면 그 이유도 알려주신다면 감사하겠습니다.
축구 좋아하는 개발자님 안녕하세요 :) 우선 말씀하신대로 visited를 global로 선언하지 않아도 정답이 잘 나오는 점 확인했습니다. 제가 여태까지 알고 있었던 global keyword는 "global 변수를 함수 내에서 수정하고자 할 때 사용한다"라고 이해해서 visited만 사용하고 graph는 따로 사용하지 않았습니다. 그런데 말씀하신대로 visited도 global을 사용하지 않아도 정답이 잘 나와서 조금 더 확인해보니 "mutable 객체는 함수 내에서 수정할 때에도 global keyword를 생략해도 된다"라는 내용을 확인했습니다. 여기서 mutable 객체의 예시로는 list, set 등이 있습니다. 즉, visited라는 2차원 list의 값을 변경하는 것은 따로 global keyword가 필요하지 않았었는데, 제가 이 부분을 immutable과 구분하지 못해서 습관처럼 썼었네요 ㅎㅎ 그래서 정리하자면 global keyword는 1) global 변수를 함수 내에서 "수정"하고자 할 때 사용하고, 조회할 때는 생략해도 된다. 2) 이마저도 mutable 객체(list, set 등)라면 생략하여도 문제(UnboundLocalError)가 발생하지 않는다. 이렇게 정리할 수 있을 것 같아요! 참고로 GeeksForGeeks에 더 확실하게 정리를 해두어서 링크도 같이 남겨요(www.geeksforgeeks.org/global-keyword-in-python/) :) 좋은 댓글 감사합니다! 저도 덕분에 global 키워드에 대해서 조금 더 정확하게 이해했습니다.
행복한 에드워드님 안녕하세요(팬입니다) :) 네 이 방법은 DFS라고 보는 게 더 정확할 것 같아요~ BFS는 주로 Queue를 관리해서 모든 경우의 수를 한 칸씩 전진한다면, 지금 같은 풀이는 하나의 경우의 수를 완성시킬 때까지 끝까지 가보는 형태이고, 재귀 함수 형태로 구현하는 게 주로 DFS 방식이라 DFS라고 보시는 게 맞을 것 같아요!
똑같이 제출했는데 왜 컴파일 에러가 뜰까요..? import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline MAX = 50 + 10 dirR = [1, -1, 0, 0] dirC = [0, 0, 1, -1] def dfs(y,x): global visited visited[y][x] = True for dirIdx in range(4): newY = y + dirR[dirIdx] newX = x + dirC[dirIdx] if graph[newY][newX] and not visited[newY][newX]: dfs(newY, newX) #0. 입력 및 초기화 T = int(input()) for _ in range(T): M, N, K = map(int, input().split()) graph = [[False]*MAX for _ in range(MAX)] visited = [[False]*MAX for _ in range(MAX)]
#1. 그래프 정보 입력 for _ in range(K): x, y = map(int, input().split()) graph[y+1][x+1] = True
#2. 방문하지 않으 지점부터 dfs 돌기 answer = 0 for i in range(1, N+1): for j in range(1, M+1): if graph[i][j] and not visited[i][j]: dfs(i,j) answer += 1 print(answer)
제가 제출했을 때는 indent error로 compile error가 발생하네요! Sorry: IndentationError: unindent does not match any outer indentation level 이럴 땐 코드가 시작되는 위치의 띄어쓰기 혹은 탭 규칙이 일정하지 않거나 잘 맞지 않아서 그런 경우가 많아요! 혹시 Visual Studio Code 같은 IDE를 사용하신다면 자동으로 포맷을 맞춰보시고, 혹시 다른 compile error가 있었다면 compile error가 발생한 에러 메세지를 알려주세요 :)
항상 감사합니다. 즐거운 금요일 되세요
네 감사합니다! :)
와 이집 알고리즘 잘하네요
감사합니다! 인프런 강의도 준비 중이라 준비되는 대로 공유 드릴게요 :)
감사합니다 덕분에 많이 알아갑니다!
좋은 댓글 감사합니다 아서_님 :) 더 좋은 영상 많이 만들어서 올릴게요!
제대로 이해한 줄 알았는데 조금만 응용해야 되는 문제만 나오면 틀리네요 ㅠㅠ
오늘도 감사합니다 좋은 주말 보내세요!!
그렇죠 ㅎㅎ 토요일 문제도 약간 응용해야 하는 문제라 같이 보셔도 좋을 것 같아요! 비슷한 유형을 한번에 몰아서 풀다 보면 훨씬 빨리 이해되실거예요 :)
@@gaebal 감사합니당
혹시 cs공부는 어떤식으로 하는게 좋을까요 비전공자라 방향을 못잡겠네요ㅠ-ㅠ
개발자로 취직하기의 DFS 강의 : inf.run/MqJT
파이썬 코드 : coding-grandpa.tistory.com/120
문제 보기 : www.acmicpc.net/problem/1012
00:00 문제 설명
04:30 정석 풀이
10:43 더 간결한 풀이
#유기농배추 #백준1012 #파이썬
정석 풀이에서 왼쪽(x-1)과 위쪽(y-1)은 빈공간을 두어 인덱스를 초과할일이 없지만
오른쪽(x+1)과 밑쪽(y+1)은 빈공간이 없어 인덱스를 초과하지 않나요??
네 최초에 배열을 선언할 때 MAX개를 만듭니다. 이때 MAX는 최댓값인 50에 10을 더해서 60개씩 만들어요~!
이론적으로는 (최댓값 + 2)개만 만들어도 충분한데, 그냥 습관이 되어 넉넉히 10개 추가해서 사용하고 있습니다 ㅎㅎ
그러면 여러모로 고려할 예외 케이스가 줄어들어서 코드도 간결해져요.
@@gaebal 답글 감사합니다!! 파이썬은 익숙하지 않아 그 부분을 캐치 못했었네요ㅠ 덕분에 DFS개념 잡고갑니다 감사합니다!!
@@Dijkstra-algorithm 네 감사합니다 :) 파이썬 공부 화이팅 하세요!
안녕하세요 개발자로 취직하기님 항상 영상 잘 보고 있습니다. 다름이 아니라 코드보고 궁금증이 생겨 댓글 남깁니다.
질문
- visited를 global로 할 필요가없을 것 같은데 하신 이유가 있나요??
- dfs 함수가 for문 안에 들어가기 때문에 동일 스콥이라 global로 할 필요없지 않을까요?? (global도 하지 않을 때 동일한 결과가 나오는 것 확임함)
- 마찬가지로 graph 변수는 global로 하지 않았지만 dfs 함수에 잘 사용하고 있는 것을 확인할 수 있습니다.
graph 변수는 global로 하지 않고 visited만 global로 하는 것이 의도된 것이면 그 이유도 알려주신다면 감사하겠습니다.
축구 좋아하는 개발자님 안녕하세요 :)
우선 말씀하신대로 visited를 global로 선언하지 않아도 정답이 잘 나오는 점 확인했습니다.
제가 여태까지 알고 있었던 global keyword는 "global 변수를 함수 내에서 수정하고자 할 때 사용한다"라고 이해해서 visited만 사용하고 graph는 따로 사용하지 않았습니다.
그런데 말씀하신대로 visited도 global을 사용하지 않아도 정답이 잘 나와서 조금 더 확인해보니 "mutable 객체는 함수 내에서 수정할 때에도 global keyword를 생략해도 된다"라는 내용을 확인했습니다. 여기서 mutable 객체의 예시로는 list, set 등이 있습니다. 즉, visited라는 2차원 list의 값을 변경하는 것은 따로 global keyword가 필요하지 않았었는데, 제가 이 부분을 immutable과 구분하지 못해서 습관처럼 썼었네요 ㅎㅎ
그래서 정리하자면 global keyword는
1) global 변수를 함수 내에서 "수정"하고자 할 때 사용하고, 조회할 때는 생략해도 된다.
2) 이마저도 mutable 객체(list, set 등)라면 생략하여도 문제(UnboundLocalError)가 발생하지 않는다.
이렇게 정리할 수 있을 것 같아요!
참고로 GeeksForGeeks에 더 확실하게 정리를 해두어서 링크도 같이 남겨요(www.geeksforgeeks.org/global-keyword-in-python/) :)
좋은 댓글 감사합니다! 저도 덕분에 global 키워드에 대해서 조금 더 정확하게 이해했습니다.
@@gaebal 답변 감사합니다. 항상 영상으로 큰 도움받고 있습니다. 앞으로도 좋은 풀이 영상 부탁드립니다!!
@@축구좋아하는개발자 네 감사합니다 :)
혹시 이 방법은 bfs 아닌가요? 궁금해서 질문드려요..
행복한 에드워드님 안녕하세요(팬입니다) :) 네 이 방법은 DFS라고 보는 게 더 정확할 것 같아요~ BFS는 주로 Queue를 관리해서 모든 경우의 수를 한 칸씩 전진한다면, 지금 같은 풀이는 하나의 경우의 수를 완성시킬 때까지 끝까지 가보는 형태이고, 재귀 함수 형태로 구현하는 게 주로 DFS 방식이라 DFS라고 보시는 게 맞을 것 같아요!
@@gaebal 감사합니다~! 두 개념이 조금 헷갈렸는데 바로 이해된 것 같아요 ㅎㅎ
@@pleasuresheeran 다행이네요!! ㅎㅎ 감사합니다~
똑같이 제출했는데 왜 컴파일 에러가 뜰까요..?
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
MAX = 50 + 10
dirR = [1, -1, 0, 0]
dirC = [0, 0, 1, -1]
def dfs(y,x):
global visited
visited[y][x] = True
for dirIdx in range(4):
newY = y + dirR[dirIdx]
newX = x + dirC[dirIdx]
if graph[newY][newX] and not visited[newY][newX]:
dfs(newY, newX)
#0. 입력 및 초기화
T = int(input())
for _ in range(T):
M, N, K = map(int, input().split())
graph = [[False]*MAX for _ in range(MAX)]
visited = [[False]*MAX for _ in range(MAX)]
#1. 그래프 정보 입력
for _ in range(K):
x, y = map(int, input().split())
graph[y+1][x+1] = True
#2. 방문하지 않으 지점부터 dfs 돌기
answer = 0
for i in range(1, N+1):
for j in range(1, M+1):
if graph[i][j] and not visited[i][j]:
dfs(i,j)
answer += 1
print(answer)
제가 제출했을 때는 indent error로 compile error가 발생하네요!
Sorry: IndentationError: unindent does not match any outer indentation level
이럴 땐 코드가 시작되는 위치의 띄어쓰기 혹은 탭 규칙이 일정하지 않거나 잘 맞지 않아서 그런 경우가 많아요! 혹시 Visual Studio Code 같은 IDE를 사용하신다면 자동으로 포맷을 맞춰보시고, 혹시 다른 compile error가 있었다면 compile error가 발생한 에러 메세지를 알려주세요 :)