Graph

백준 1260번 바로가기 나의 풀이 edgeList = [] n, m, v = map(int, input().split()) for _ in range(m): a, b = map(int, input().split()) edgeList.append((a, b)) edgeList.append((b, a)) def dfs(adjacencyList, root): stack = [root] visitedList = [] while stack: current = stack.pop() if current not in visitedList: visitedList.append(current) temp = adjacencyList[current - 1] temp.sort(reverse=True) stack += temp return visitedList def bfs(adjacencyList, root): from collections import deque queue = deque([root]) visitedList = [] while queue: current = queue.popleft() if current not in visitedList: visitedList.append(current) temp = adjacencyList[current - 1] temp.reverse() queue += temp return visitedList adjacencyList = [[] for _ in range(n)] for edge in edgeList: adjacencyList[edge[0] - 1].append(edge[1]) print(*dfs(adjacencyList, v)) print(*bfs(adjacencyList, v)) CODE REVIEW DFS와 BFS를 구현하고 방문한 Node(Vertex)를 순서대로 출력하는 문제였다. 중간 순서가 자꾸 꼬여서 코드를 살펴봤는데, current에 연결된 vertex를 저장할 때에 stack/queue를 reverse 시켜줘야 했다. 그래프 이론의 기본 DFS & BFS에 대해서는 이제 어느정도 익숙해졌는데, 더 상위 문제를 풀어가며 그래프 이론을 더 알아가봐야겠다.

백준 16173번 바로가기 나의 풀이 import sys sys.setrecursionlimit(10**6) n = int(input()) maps = [] for i in range(n): lines = map(int,input().split()) maps.append(list(lines)) visited = [[False] * n for _ in range(n)] def dfs(x,y): if not 0<=x<n or not 0<=y<n: return l = maps[y][x] if l == -1: print("HaruHaru") exit(0) if not visited[y][x]: visited[y][x] = True dfs(x+l,y) dfs(x,y+l) return dfs(0,0) print("Hing") 고수의 풀이 import sys from collections import deque def solution(N, graph): visited = [[False] * N for _ in range(N)] dx = [1, 0] dy = [0, 1] def dfs(x, y, visited): queue = deque() queue.append((x, y)) while queue: x, y = queue.popleft() if graph[x][y] == -1: return 'HaruHaru' jump = graph[x][y] # 점프 값 for i in range(2): nx = x + dx[i] * jump ny = y + dy[i] * jump if nx >= N or ny >= N: continue if visited[nx][ny]: continue else: visited[nx][ny] = True queue.append((nx, ny)) return 'Hing' print(dfs(0, 0, visited)) if __name__ == "__main__": N = int(sys.stdin.readline()) graph = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] solution(N, graph) 출처 ...

백준 2644번 바로가기 나의 풀이 n = int(input()) a,b = map(int,input().split()) m = int(input()) vertexList = [[] for _ in range(n+1)] visitedList = [False] * (n+1) result = [] for _ in range(m): x,y = map(int, input().split()) vertexList[x].append(y) vertexList[y].append(x) def dfs(vertex, num): num += 1 visitedList[vertex] = True if vertex == b: result.append(num) for vertex in vertexList[vertex]: if not visitedList[vertex]: dfs(vertex, num) dfs(a,0) if not result: print(-1) else: print(result[0]-1) CODE REVIEW 그래프 이론을 이용하여 촌수를 구하는 문제. DFS 함수 구현 과정에서 예상한 결과와 실행값이 달라서 고민을 많이 했다. vertexList와 visitedList를 만들 때에 range(n+1)로 잡으면 index번호와 vertex번호가 같아져서 편리해진다.

백준 4963번 바로가기 나의 풀이 import sys sys.setrecursionlimit(10**6) def check(x,y): if not 0<=x<h or not 0<=y<w: return False if maps[x][y] == 1: maps[x][y] = 0 check(x-1,y+1) check(x,y+1) check(x+1,y+1) check(x-1,y) check(x+1,y) check(x-1,y-1) check(x,y-1) check(x+1,y-1) return True return False import sys for i in sys.stdin: if i == "0 0\n": break w,h = map(int,i.split()) maps = [[] for _ in range(h)] for i in range(h): for k in input().split(): maps[i].append(int(k)) count = 0 for i in range(w): for j in range(h): if check(j,i): count += 1 print(count) 다른 풀이 구경하기 import sys input=sys.stdin.readline sys.setrecursionlimit(10000) dx=[1,0,-1,0,1,1,-1,-1] dy=[0,1,0,-1,1,-1,-1,1] def dfs(x,y): graph[x][y]=0 for i in range(8): nx=x+dx[i] ny=y+dy[i] if 0<=nx<h and 0<=ny<w and graph[nx][ny]==1: dfs(nx,ny) while True: w,h=map(int,input().split()) if w==0 and h==0: break graph=[] count=0 for i in range(h): graph.append(list(map(int,input().split()))) for i in range(h): for j in range(w): if graph[i][j]==1: dfs(i,j) count+=1 print(count) 출처 ...

백준 1012번 바로가기 나의 풀이 import sys sys.setrecursionlimit(10**6) def check(x,y): if not 0<=x<n or not 0<=y<m: return False if graph[x][y] == 1: graph[x][y] = 0 check(x-1,y) check(x+1,y) check(x,y-1) check(x,y+1) return True return False t = int(input()) for _ in range(t): m, n, k = map(int, input().split()) graph = [[0] * m for _ in range(n)] for _ in range(k): a, b = map(int, input().split()) graph[b][a] = 1 count = 0 for i in range(n): for j in range(m): if check(i,j): count += 1 print(count) CODE REVIEW 그래프 이론을 응용한 문제. 문제 조건을 그래프 이론을 활용할 수 있는 형태로 조작하는 과정에 대한 발상이 쉽지 않았다. 기본적인 아이디어는 힌트를 얻어가며 코드를 작성했다. DFS 탐색과정에서 for문이 일정 횟수 이상 넘어가다보니 recursion error이 발생했다. 백준에서는 이러한 런타임 에러에 대한 해결법을 제공하는데, sys.setrecursionlimit()을 이용해서 코드 수정 없이 문제를 해결했다. check(x,y)부분의 발상이 너무 어려웠다. 재귀 함수를 적재적소에 잘 써먹자!