Graph

백준 21736번 바로가기 나의 풀이 # 입력 import sys from collections import deque n,m = map(int,sys.stdin.readline().split()) maps = [list(sys.stdin.readline().strip()) for _ in range(n)] visited = [[False] * m for _ in range(n)] dx = [0,0,1,-1] dy = [1,-1,0,0] # 처리 def bfs(where): count = 0 i,j = where[0],where[1] queue = deque() visited[i][j] = True queue.append((i,j)) while queue: i, j = queue.popleft() for k in range(4): x = i + dx[k] y = j + dy[k] if 0<=x<n and 0<=y<m and not visited[x][y]: if maps[x][y] != 'X': queue.append((x,y)) visited[x][y] = True if maps[x][y] == 'P': count += 1 return count def get_index(maps, target): for idx1, i in enumerate(maps): for idx2, j in enumerate(i): if j == target: return idx1, idx2 ans = bfs(get_index(maps, 'I')) print('TT' if ans == 0 else ans) CODE REVIEW graph을 이용해서 탐색하는 문제. 탐색하는 과정에서 현재 queue에서 꺼낸 값이 무엇이냐에 따라서 조건을 분기시키는 것이 핵심이었다. ‘I’의 위치를 구하기 위해서 enumerate을 두 번 사용해서 위치를 파악했다. 다른 방법으로는 전체를 탐색하는 방법이 있다. for i in range(n): for j in range(m): if maps[i][j] == 'I': print(i,j) break

백준 10026번 바로가기 나의 풀이 # 입력 import sys from collections import deque sys.setrecursionlimit(10**6) n = int(sys.stdin.readline().strip()) maps = [[] * n for _ in range(n)] for i in range(n): maps[i] = list(sys.stdin.readline().strip()) count = 0 visited = [[False] * n for _ in range(n)] dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] # 처리 def bfs(i, j, color): queue = deque() queue.append([i, j]) visited[i][j] = True while queue: i, j = queue.popleft() for k in range(4): x = i + dx[k] y = j + dy[k] if not 0 <= x < n or not 0 <= y < n or visited[x][y]: continue if color == maps[x][y]: visited[x][y] = True queue.append([x, y]) return for i in range(n): for j in range(n): if visited[i][j] == False: bfs(i, j, maps[i][j]) count += 1 print(count, end=" ") def bfs_blind(i, j, color): queue = deque() queue.append([i, j]) visited[i][j] = True while queue: i, j = queue.popleft() for k in range(4): x = i + dx[k] y = j + dy[k] if not 0 <= x < n or not 0 <= y < n or visited[x][y]: continue if color == "B" and maps[x][y] == "B": visited[x][y] = True queue.append([x, y]) elif color != "B" and maps[x][y] != "B": visited[x][y] = True queue.append([x, y]) return count = 0 visited = [[False] * n for _ in range(n)] for i in range(n): for j in range(n): if visited[i][j] == False: bfs_blind(i, j, maps[i][j]) count += 1 print(count) CODE REVIEW graph을 이용한 문제. 백준 4963번에서는 0,1 두 개만 고려해서 구역을 나누면 되었다면, 10026번에서는 RGB 3종류를 고려해서 구역을 나누어야해서 고려할 부분이 많았다. 적록색맹의 경우 구역의 갯수를 구하는 과정에서 미리 RG를 K와 같이 처리해주고 문제를 풀지, 아니면 탐색 과정에서 두 경우를 고려해줄지 고민하다가 탐색 과정에서 처리하는 방식을 택했다.

백준 11725번 바로가기 나의 풀이 # 입력 import sys n = int(sys.stdin.readline().strip()) graph = {} for _ in range(n-1): a,b = map(int, sys.stdin.readline().split()) if a in graph: graph[a].append(b) else: graph[a] = [b] if b in graph: graph[b].append(a) else: graph[b] = [a] visitedList = [False]*n parent = {} # 처리 def BFS(graph, node, visitedList): from collections import deque queue = deque([node]) visitedList[node-1] = True while queue: temp = queue.popleft() for i in graph[temp]: if not visitedList[i-1]: queue.append(i) visitedList[i-1] = True parent[i] = temp BFS(graph, 1, visitedList) for i in sorted(parent.items()): print(i[1]) CODE REVIEW BFS을 활용한 문제. 각 node별로 부모 node를 구하는 문제였다. 방향성이 없는 연결이라 (a,b)에 대해서 graph[a]=b graph[b]=a 모두 graph에 포함시켜야하는걸 잊지 말자. dictionary의 key를 기준으로 정렬하기 위해서는 sorted(dict.items())를 활용하면 된다. 그러면 (key,value)쌍으로 된 List를 리턴해준다.

백준 1697번 바로가기 내 풀이 # 입력 import sys n, k = map(int, sys.stdin.readline().split()) from collections import deque queue = deque([n]) visitedList = [False]*100001 count = 0 # 처리 while queue: if k in queue: print(count) break count += 1 for _ in range(len(queue)): temp = queue.popleft() if not visitedList[temp]: next = [temp-1,temp+1,temp*2] for n in next: if 0<=n<=100000 and visitedList[n]==False: queue.append(n) visitedList[temp] = True CODE REVIEW BFS를 응용한 문제. 100,001개의 node을 가진 graph를 구해놓고 최소경로를 구하는 방법도 있겠지만, 메모리나 시간적으로 매우 비효율적이다. 따라서 초기 queue에 n을 집어놓고 BFS로 나아가면서 k가 queue에 등장하는지 확인하는 방법으로 구현했다. count를 구현하는 과정에서 꽤나 애를 먹었다… 처음에는 count=[0]*100001 count[n]=count[temp]+1로 두고 풀었는데, count를 탐색하는 과정에서 시간을 많이 잡아먹어서 아예 구조를 바꾸었다. for _ in range(len(queue))로 BFS 한 층이 다 마무리 될 때까지 loop를 돌리는 방식으로, loop마다 count를 1씩 올려가며 탐색을 진행하니 시간 문제 없이 해결되었다.

백준 17626번 바로가기 나의 풀이 # 입력 import sys n = int(sys.stdin.readline().strip()) squares = [i**2 for i in range(1,int(n**0.5)+1)] queue = [n] count = 0 # 처리 - bfs 활용 while len(queue) > 0: count += 1 temp = set() for q in queue: for s in squares: if q < s: break temp.add(q-s) if 0 in queue: break queue = list(temp) print(count-1) 고수의 풀이 dp = [50001 for i in range(n + 1)] dp[0] = 0 for i in range(1, n + 1): for j in range(1, i + 1): val = j * j if val > i: break dp[i] = min(dp[i], dp[i - val] + 1) print(dp[n]) 출처 CODE REVIEW 처음에는 제곱수들을 역순으로 배열해서 차례대로 빼면 되겠지 생각했지만, 그게 최선의 수가 아니라는걸 깨달았다… bfs을 응용해서 n에서 0까지 top2bottom 방식으로 알고리즘을 구상했다. BFS(너비 우선 탐색) 방식이 층별로 내려가는 식이라 과정이 유사하다는 점에서 착안했다. dp로는 도저히 풀어내는 방법을 모르겠어서 다른 사람의 풀이를 참고했다. 짧고 깔끔하게 잘 짰구만…👍👍 min(dp[i], dp[i-val]+1) 발상이 쉽지 않다. 허허