분류 전체보기

문제 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 코드 My answer(시간초과)-재귀 def find_route(x,y,tmp,lim,cnt): if(x>=lim or y>=lim or tmp[x][y]==0): if(x==lim-1 and y==lim-1): return 1 return 0 elif(x==lim-1 and y==lim-1): return 1 else: if(x+tmp[x][y]

문제 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 코드 My answer import sys input=sys.stdin.readline n=int(input()) tmp,price=[],[] for i in range(n): tmp.append(list(map(int,input().split()))) tmp.append([0,0]) price=[i[1] for i in tmp] for i in range(n-1,-1,-1): if(i+tmp[i][0]>n): price[i]=..

오늘은 BFS 너비우선탐색에 대해서 설명하겠다. 저번 DFS에서 간단하게 말했었는데 다시 설명하겠다. DFS와 구별하면서 이해하는게 훨씬 쉽다. DFS는 한분기의 끝까지 탐색하고 아니면 돌아오고 다시 끝까지가고를 반복하는데, BFS는 "너비" 우선탐색이므로 한단계를 전부 탐색하고 다음 깊이로 들어간다. 즉 루트로부터 가까운 애들을 먼저 탐색한후 점점 멀어진다. 너비우선탐색은 최단경로나 임의의 경로를 찾을 때 쓰인다. DFS는 재귀로 구현을 했는데, WBS는 보통 QUE를 의 선입선출을 이용해서 코드를 구현한다. 이때 주의할점은 반드시 방문한 노드를 기억하는 코드가 있어야된다는 곳이다. 방문만하고 기억하지않으면 무한루프에 빠지게 된다. from collections import deque def bfs(g..

문제 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 코드 Another answer import sys from collections import deque input = sys.stdin.readline() def bfs(): q = deque() q.append(n) while q: x = q.popleft() if x == k: print(dist[x]) break for j in (x-1,x+1,x*2): if 0

문제 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 코드 My answer import sys from itertools import permutations n,cost=int(input()),0 city,result=[],1000000*n order=[i for i in range(n)] for i in range(n): city.append(list(map(int,sys.stdin.readline().split()))) for i in permutations(o..

문제 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 코드 My answer import random from itertools import permutations n=int(input()) answer,tanswer=0,0 tmp=list(map(int,input().split())) for i in permutations(tmp,n): for j in range(len(i)): if(j!=len(i)-1): tanswer+=abs(i[j]-i[j+1]) answer=max(tanswer,answer) tanswer=0 p..