Most Muscular Most Muscular

기출: BOJ #2178 n, m = map(int,input().split()) visited = [[False for _ in range(m)]for __ in range(n)] board = list() dx,dy = [1,-1,0,0],[0,0,1,-1] for _ in range(n): row = list() inputStr = input() for j in range(m): row.append(int(inputStr[j])) board.append(row) queue = [[[0,0],1]] visited[0][0] = True while queue: cur = queue.pop(0) curX, curY = cur[0][0], cur[0][1] curVal = cur[1] if curX==n-..

기출: BOJ #1697 탐색하는 방법으로 +1, -1, *2가 있다 n, k = map(int,input().split()) maxVal = 100000 board = [False for _ in range(0, maxVal+1)] queue = [[n,0]] board[n] = True while queue: cur = queue.pop(0) curX = cur[0] curVal = cur[1] if curX == k: print(curVal) break for case in range(3): nextX, nextVal = 0, curVal + 1 # +1 if case==0: nextX = curX + 1 # -1 elif case==1: nextX = curX -1 # *2 else: nextX ..

기출: BOJ #7562 dx, dy = [2,2,1,1,-1,-1,-2,-2],[1,-1,2,-2,2,-2,1,-1] tc = int(input()) for _ in range(tc): n = int(input()) board = [] visited = [[False for _ in range(n)] for __ in range(n)] start = list(map(int,input().split())) targetX, targetY = map(int,input().split()) queue = [[start,0]] while queue: cur = queue.pop(0) curX, curY = cur[0][0], cur[0][1] curVal = cur[1] if curX==targetX and cu..

기출: BOJ #4963 일반적인 BFS문제와 다른 점은 다음과 같다 1. 입력 종료 조건은 "0 0"의 입력이다 2. 같은 섬의 조건은 대각선을 포함한다 입력을 미리 받아 놓으려면 (입력의 개수가 정해지지 않은 경우) sys.stdin.readline() 함수를 사용하면 된다 from sys import stdin lines = stdin.readlines() dx, dy = [1,1,1,0,0,-1,-1,-1], [1,0,-1,1,-1,1,0,-1] while lines: y, x = map(int,lines.pop(0).split()) if y==0 and x==0: break ans = 0 visited = [[False for __ in range(y)] for _ in range(x)] boa..

기출: BOJ #11724 일반적인 BFS 문제이다 n,m = map(int,input().split()) graph = dict() visited = [False for _ in range(n+1)] ans = 0 for i in range(n+1): graph[i] = list() for _ in range(m): x, y = map(int,input().split()) graph[x].append(y) graph[y].append(x) def BFS(x): visited[x] = True queue = [x] while queue: cur = queue.pop(0) for next in graph[cur]: if visited[next]: continue visited[next] = True que..

기출: BOJ #1260 그래프 탐색 대표 문제이다 다음 조건을 만족해야 한다 1. 탐색 순서는 낮은 번호의 정점부터 방문한다 2. 두 정점 사이 여러개의 간선이 존재할 수 있다 낮은 번호의 정점부터 방문하려면 각 정점과 연결된 정점들을 정렬해줘야 한다 두 정점 사이 여러 개의 간선이 존재할 수 있지만 하나의 간선만을 사용하므로 하나의 간선만 추가시켜준다 n,m,v = map(int,input().split()) graph = dict() bfsAns, dfsAns = list(), list() bfsVisited, dfsVisited = [False for _ in range(n+1)], [False for _ in range(n+1)] # 그래프 초기화 for i in range(n+1): graph..

기출 : BOJ #12865 현재 상황을 무게가 N이라고 가정했을 때 현재 무게일때 가치의 최댓값(D[n])은 (직전 최댓값(D[n-ai])에 직전에 선택한 물건의 가치(val[ai])를 더한 것)의 최댓값이다 이를 점화식으로 표현하면 다음과 같다 D[n] = max(D[n-ai]+val[ai]) from copy import deepcopy # D[n] = 무게가 n일때 가질 수 있는 가치의 최댓값, [최댓값을 만들 때 선택된 것들] # D[n] = max(D[n-ai]+val[ai]) ans = 0 n, k = map(int,input().split()) weight, val = list(), list() for i in range(n): w, v = map(int,input().split()) we..

기출 : BOJ #1932 n번째 줄 m번째 위치를 고르는 경우 이는 n-1번째 줄의 m-1번째, m번째 위치로부터 내려온다 (확장성) 이를 고려하면 점화식은 다음과 같다 D[n][m] = n번째 줄 m번째 숫자를 고르는 경우 최댓값 D[n][m] = max(D[n-1][m-1], D[n-1][m]) + tri[n][m] # d[n][m] = max(d[n-1][m-1], d[n-1][m]) + tri[n][m] n = int(input()) tri = list() d = [[0 for j in range(i+1)] for i in range(n)] for _ in range(n): tri.append(list(map(int,input().split()))) d[0][0] = tri[0][0] for i..