Posts

백준 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) 출처 ...

백준 2579번 바로가기 나의 풀이 s = [] for _ in range(n:=int(input())): s.append(int(input())) points = [0]*n if n < 3: print(sum(s)) else: points[0] = s[0] points[1] = s[0] + s[1] points[2] = max(s[1]+s[2],s[0]+s[2]) for i in range(3,n): points[i] = max(points[i-2], points[i-3]+s[i-1]) + s[i] print(points[-1]) CODE REVIEW 중학교 창의력 수학 경시대회 단골소재 계단 오르기. 한 계단 또는 두 계단이라는 표현은 질릴도록 봤다. case별로 쪼개서 점화식을 설정하고 풀어내면 된다. 전 단계를 밟는 경우와/밟지 않는 경우로 나누면 모든 경우를 커버할 수 있다. max(points[i-2], points[i-3]+s[i-1]) 부분이 조금 까다롭긴 했는데 그외에는 무난한 문제였다.

백준 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) 출처 ...