Graph

백준 2178번 바로가기 나의 풀이 # 입력 import sys read = sys.stdin.readline n,m = map(int, read().split()) maze = [] for _ in range(n): maze.append(list(map(int,read().strip()))) dx = [1,-1,0,0] dy = [0,0,1,-1] # 처리 - bfs 활용 def bfs(x, y): from collections import deque queue = deque() queue.append((x,y)) while queue: x,y = queue.popleft() for i in range(4): new_x = x+dx[i] new_y = y+dy[i] if 0<=new_x<n and 0<=new_y<m and maze[new_x][new_y] == 1: queue.append((new_x,new_y)) maze[new_x][new_y] = maze[x][y] + 1 bfs(0,0) print(maze[n-1][m-1]) CODE REVIEW 처음에는 DFS을 이용해서 문제를 풀어내려하다가 최적값을 찾는데 애를 먹었다. 미로찾기 문제에서 최단경로를 찾기 위해서는 BFS가 편리하다. 어느정도 난이도 있는 문제를 풀 때에 무작정 풀어나가지 말고, 어떤 전략이 나을지 고민해보는 자세를 가지자!

백준 2667번 바로가기 DFS을 이용한 풀이 # 입력 import sys read = sys.stdin.readline n = int(read().strip()) graph = [] for _ in range(n): graph.append(list(map(int, read().strip()))) dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] # 처리 - dfs 활용 def DFS(x, y): if not 0<=x<n or not 0<=y<n: return False if graph[x][y] == 1: global count count += 1 graph[x][y] = 0 for i in range(4): nx, ny = x + dx[i], y + dy[i] DFS(nx, ny) return True return False count = 0 ans = [] for i in range(n): for j in range(n): if DFS(i,j): ans.append(count) count = 0 print(len(ans)) for a in sorted(ans): print(a) BFS를 이용한 풀이 # 입력 import sys read = sys.stdin.readline n = int(read().strip()) graph = [] for _ in range(n): graph.append(list(map(int, read().strip()))) dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] # 처리 - BFS 활용 def BFS(x, y): from collections import deque queue = deque([(x,y)]) graph[x][y] = 0 count = 1 while queue: x,y = queue.popleft() for i in range(4): nx, ny = x + dx[i], y + dy[i] if 0<=nx<n and 0<=ny<n and graph[nx][ny] == 1: graph[nx][ny] = 0 queue.append((nx,ny)) count += 1 return count count = 0 ans = [] for i in range(n): for j in range(n): if graph[i][j] == 1: ans.append(BFS(i,j)) count = 0 print(len(ans)) for a in sorted(ans): print(a) CODE REVIEW DFS와 BFS 두 방법으로 풀 수 있는 문제였다. BFS의 경우 queue을 이용해서 차례대로 구역 안의 1인 영역을 찾아내었고, DFS의 경우 재귀를 통해 찾아내었다.

백준 11724번 바로가기 나의 풀이 from collections import deque import sys # 입력 n, m = map(int,sys.stdin.readline().split()) graph = dict() visited = [False] * (n+1) count = 0 for _ in range(m): u, v = map(int,sys.stdin.readline().split()) if u in graph: graph[u].append(v) else: graph[u] = [v] if v in graph: graph[v].append(u) else: graph[v] = [u] # 처리 def dfs(graph, queue): while queue: c = int(queue.pop()) if visited[c] == False: visited[c] = True if c in graph: queue += deque(graph[c]) for i in range(1, n+1): if visited[i] == False: dfs(graph, deque([i])) count += 1 print(count) CODE REVIEW dfs 또는 bfs를 이용해서 풀어낼 수 있는 문제. 시간을 단축시키기 위해 시간복잡도가 O(1)인 dict()로 graph를 저장했다. 다만, 이 경우 graph에서 요소를 뽑아올 때에 없는 index를 가져오려 하면 KeyError가 발생하므로 예외 처리를 해주어야 한다. 위 코드에서 if c in graph: 부분이 없다면, KeyError가 발생하는데 아마도 edge없이 홀로 남아있는 vertex의 경우 에러가 발생하는 듯 하다.

백준 7569번 바로가기 나의 풀이 from collections import deque # 입력 m,n,h=map(int,input().split()) tomato = [] for i in range(h): tomato.append([list(map(int,input().split())) for _ in range(n)]) queue = deque([]) dx = [-1,1,0,0,0,0] dy = [0,0,-1,1,0,0] dz = [0,0,0,0,-1,1] # 처리 for i in range(h): for j in range(n): for k in range(m): if tomato[i][j][k] == 1: queue.append([i,j,k]) def ripe(): while queue: x,y,z = queue.popleft() for i in range(6): nx = x + dx[i] ny = y + dy[i] nz = z + dz[i] if 0<=nx<h and 0<=ny<n and 0<=nz<m and tomato[nx][ny][nz] == 0: tomato[nx][ny][nz] = tomato[x][y][z] + 1 queue.append([nx,ny,nz]) ripe() ans = 0 for t1 in tomato: for t2 in t1: for t3 in t2: if t3 == 0: print(-1) exit(0) ans = max(ans ,max(t2)) print(ans-1) CODE REVIEW 7569번 토마토의 3차원 버전. 기본 원리는 동일해서 조금만 수정하면 금세 구현할 수 있다. 이 문제도 마지막에 3차원 array에서 최댓값을 구하는 과정이 까다로웠는데, 3차원은 한번에 최댓값을 구할 수 없다. ans = max(ans,max(t2))와 같이 3차원 배열을 2차원들로 쪼개서 각각의 max값을 비교해서 더 큰 값으로 업데이트 하는 방법으로 구할 수 있다.

백준 7576번 바로가기 나의 풀이 from collections import deque # 입력 m,n=map(int,input().split()) tomato = [list(map(int,input().split())) for _ in range(n)] queue = deque([]) dx = [-1,1,0,0] dy = [0,0,-1,1] # 처리 for i in range(n): for j in range(m): if tomato[i][j] == 1: queue.append([i,j]) def ripe(): while queue: x,y = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0<=nx<n and 0<=ny<m and tomato[nx][ny] == 0: tomato[nx][ny] = tomato[x][y] + 1 queue.append([nx,ny]) ripe() for i in range(n): for j in range(m): if tomato[i][j] == 0: print(-1) exit(0) print(max(map(max, tomato))-1) CODE REVIEW 2606번-바이러스문제와 1012번-유기농 배추와 결이 같은 문제. graph 문제를 풀다보니 이제는 다 비슷비슷해 보인다. stack에 익어있는 토마토를 집어놓고 하나씩 꺼내가며 옆의 토마토들을 익히는 과정을 반복한다. 모두 반복하고 마지막 결과물에서 익지 않은 토마토가 있는지 확인하고, 최댓값을 출력한다. 논리상에 문제가 없는데 2%에서 자꾸 틀렸습니다라길래 코드를 살펴봐도 문제를 찾을 수 없었다. 알고보니 출력 부분에서 최대값을 찾는 과정에서 문제가 생긴 것! 2차원 배열의 경우 그냥 max(max(array))로 구하면 안되고, max(map(max,array))로 구해야 한다. 7569번 토마토는 3차원 배열이던데 이것도 도전해보자.