나만의 개발블로그

풀이 지역의 높이 중 가장 큰 값을 구한 다음 해당 지역의 높이 전까지 반복문을 돌려 height를 기준으로 안전한 영역의 최대 개수를 출력 import sys from collections import deque input = sys.stdin.readline def bfs(height): while q: y,x = q.popleft() for ny,nx in [[-1,0],[1,0],[0,-1],[0,1]]: dy,dx = y+ny,x+nx if 0

풀이 bfs를 사용해서 풀었으며 적록색약의 경우는 visit1과 bfs1로 아닐 경우엔 visit2와 bfs2로 풀 수 있도록 해결 import sys from collections import deque def bfs1(): while q: y,x = q.popleft() for ny,nx in [[-1,0],[1,0],[0,-1],[0,1]]: dy,dx = y+ny,x+nx if 0

풀이 단순히 a 와 b의 값을 2로 나눈 몫이 해당 노드의 부모가 되기에 같아질 경우 *10을 한 값을 제출 import sys n = int(sys.stdin.readline()) for _ in range(n): a, b = map(int, sys.stdin.readline().split()) while True: if a == b: print(a * 10) break if a > b: a //= 2 else: b //= 2

풀이 start를 이용해서 연결되어 있는 국가가 하나인 경우를 찾고자 했음 굳이 안해도 되는 것 같음 아래 코드는 일반적인 방문 체크를 통해 풀이하는 코드 특징으로는 bfs를 통해 풀었기에 q에 추가할 때 방문 체크를 하여 같은 나라가 q에 똑같이 들어있지 않도록 하기! import sys input = sys.stdin.readline from collections import deque for _ in range(int(input())): n,m = map(int,input().split()) _dic = {i:[] for i in range(1,n+1)} result = 0 for _ in range(m): a,b = map(int,input().split()) _dic[a].append(b) _d..

풀이 단순히 '상하좌우'만 탐색하는 문제가 아닌 대각선까지 탐색을 하는 문제이기에 좌표를 총 8개를 추가해 탐색하는 과정을 거쳤으며 입력이 계속 주어지고, 마지막에는 0,0 의 입력이 주어지기에 조건을 추가해 멈출 수 있도록 해결 import sys from collections import deque input = sys.stdin.readline while True: w,h = map(int,input().split()) if not w and not h: break arr = [list(map(int,input().rstrip('\n').split())) for _ in range(h)] visit = [[0]*w for _ in range(h)] result = 0 for i in range(h)..

처음에는 방문을 할 필요가 있을까라는 생각에 방문 없이 제출을 했는데 메모리 초과가 발생해서 방문 체크 후 제출을 했지만 그래도 여전히 시간 초과... 그래서 혹시나 하는 마음에 pypy로 제출을 하니 꾸역꾸역 제출은 완료됐는데... 이게 맞는건가 싶네 풀이 과정 문제를 처음 접했을 때 A가 B를 신뢰하는 경우 B를 해킹하면, A도 해킹할 수 있다는 말에 ??? 그러면 반대로 방향있는 선을 만들어야겠다 생각해서 만들어둔 arr에 arr[b].append(a)로 추가 이후 평범한 bfs로 문제 풀이하며 반복문이 순회 마지막에 해당 값이 큰지에 대한 여부 파악 후 마지막 출력 조건에 사용 import sys from collections import deque input = sys.stdin.readline..

풀이 방식 방향이 없는 그래프기에 노드간 연결을 서로 해주는 형식으로 했고 노드 수 만큼 반복문을 돌려서 방문하지 않았다면 해당 값에 대한 _dic의 값을 q에 넣고 돌리기 이후 방문하지 않은 노드들은 i의 값을 visit에 넣어 방문 표시하기 이후 visit의 중복을 줄이고 0번째 노드는 없으니 -1 해서 푼 풀이 조금 시간이 상대적으로 나오긴하지만.. ㅎ import sys from collections import deque input = sys.stdin.readline n,m = map(int,input().split()) _dic = {i:[] for i in range(1,n+1)} visit = [0]*(n+1) for _ in range(m): u,v = map(int,input().sp..

풀이 방식 q에 넣어서 하나씩 조사를 하며 방문한거라면 추가하지 않고, 방문하지 않았을 때만 추가하면서, 추가시 방문 표시를 해서 중복으로 추가되지 않도록 하기 그리고 n-1, n+1, n*2 와 그 숫자에 대한 카운팅을 함께 넘겨주기 if 문으로 0

import sys from collections import deque input = sys.stdin.readline m,n = map(int,input().split()) arr = [list(map(int,input().strip('\n').split())) for _ in range(n)] visit = [[0]*m for _ in range(n)] q = deque([]) result = 0 # --------- bfs로 탐색하며 함께 나아가야 양측에서 방문하고 # --------- 같은 곳을 방문하지 않을 수 있기에 미리 1을 찾기 for i in range(n): for j in range(m): if arr[i][j] == 1: visit[i][j] = 1 q.append([i,j,0])..

해당 문제는 일반적인 그래프 문제로 방문 여부에 대한 체크를 하며 카운팅을 해 푼 풀이법 import sys from collections import deque input = sys.stdin.readline n = int(input()) arr = [list(map(int,input().strip('\n'))) for _ in range(n)] visit = [[0]*n for _ in range(n)] stack = deque([]) result = [] r_cnt = 0 for i in range(n): for j in range(n): if arr[i][j] and not visit[i][j]: cnt, r_cnt = 1, r_cnt + 1 visit[i][j] = 1 stack.append([..