어읽로꾸거

백준 6118 링크 https://www.acmicpc.net/problem/6118 6118번: 숨바꼭질 문제 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재석이는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2

백준 6087 링크 https://www.acmicpc.net/problem/6087 풀이 각 칸마다 최소 몇번의 거울을 써서 이동했나를 저장해 가면서 다익스트라로 풀었습니다. 그냥 큐로 푼사람도 있던데 조금 더 생각을 해봐야 할 것 같은... 특이한 점은 같은 회수의 거울을 이용 하더라도 온 방향이 다를 경우엔 답이 달라질 수 있으므로 저장된 최소 비용 >= 현재비용 으로 비교를 하였습니다. 조금 더 생각해본 결과 레이저 처럼 쭉쭉 뻗어나간다는 생각을 도입해보면 큐를 이용할 수 있다고 생각하여 다시 구현해보았습니다. 큐를 이용한 방법을 쓰니까 조금 더 빠르네요 코드 #다익스트라 import heapq input = __import__('sys').stdin.readline m,n = map(int, i..

백준 1926 링크 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다. www.acmicpc.net 풀이 🙄 코드 from collections import deque input=__import__('sys').stdin.readline n,m = map(int, input().split()) mp = [list(map(int, input().split())) ..

백준 2206 링크 https://www.acmicpc.net/problem/2206 풀이방법 파이썬으로 dequeue를 쓰는게 안 익숙해서 이상한데서 시간을 끌었다... 그냥 pop하면 안되고 popleft해야됨.. 만약 pop을 시키지 않고 맨 앞의 요소에 그냥 접근만 하고싶으면 q[0] 으로 할 수 있어요 처음엔 깔끔하게 짠거같은데 오류 잡는다고 이것저것 확실히 하다보니까 더러워진 느낌 저는 이 문제를 풀때 dp[y][x][벽을 뚫고 지나갔는지 여부]이걸 통해서 풀었지만, 다시 한번 생각해보니 dp[y][x]로만 해도 충분하다고 생각했었습니다. 왜냐하면, 벽을 뚫었는지 여부는 그냥 큐를 통해서 기록해주면 된다고 생각했기 때문입니다. 이미 뚫고 지나갔는지 확인해서 이미 뚫었다면 벽을 안지나가면 되는거..

백준 1854 링크 https://www.acmicpc.net/problem/1854 문제 풀이 dp[현재위치][k번째로 빨리 도착함]배열을 이용해 풀었습니다. 어제 푼 문제인 도로포장 과 상당히 비슷한 문제라는 생각이 드네요 BOJ 1162 도로포장 백준 1162 도로포장 링크 https://www.acmicpc.net/problem/1162 1162번: 도로포장 문제 준영이는 매일 서울에서 포천까지 출퇴근을 한다. 하지만 잠이 많은 준영이는 늦잠을 자 포천에 늦게 도착하기 일쑤다. 돈.. postbarca.tistory.com 파이썬으로 문제를 풀다보니까 Cpp랑 다른점이 많이 있네요 input=__import__('sys').stdin.readline 이 한줄이 없으면 시간초과 때문에 Python3..

백준 1743 링크 https://www.acmicpc.net/problem/1743 문제풀이 파이썬으로 dfs등의 재귀함수를 이용할때 주의해야 할 점은 파이썬은 재귀를 1000번 까지만 허용합니다. 그래서 이 문제같이 최대 100*100 = 10000번을 재귀로 돌아서 1000번 이상 재귀를 돌 경우에선 import sys sys.setrecursionlimit(100000) 를 입력해주어 재귀의 제한을 풀어줘야 합니다. 코드에선 10만번정도로 제한을 늘려놓았습니다. 이걸 몰라서 런타임에러를 계속 두드려맞았네요. 코드 import sys sys.setrecursionlimit(100000) def dfs(y,x,result): result=result+1 M[y][x]=0 for _ in range(0..

백준 1162 도로포장 링크 https://www.acmicpc.net/problem/1162 1162번: 도로포장 문제 준영이는 매일 서울에서 포천까지 출퇴근을 한다. 하지만 잠이 많은 준영이는 늦잠을 자 포천에 늦게 도착하기 일쑤다. 돈이 많은 준영이는 고민 끝에 K개의 도로를 포장하여 서울에서 포천까지 가는 시간을 단축하려 한다. 문제는 N개의 도시가 주어지고 그 사이 도로들과 이 도로를 통과할 때 걸리는 시간이 주어졌을 때 최소 시간이 걸리도록 하는 K개의 이하의 도로를 포장하는 것이다. 여기서 도로를 포장하게 되면 도로를 지나는데 걸리는 시간이 0이라 하자. www.acmicpc.net 문제풀이 dp[지금도시위치][도로 포장한 회수] 배열을 만들어 비교하였습니다. 큐에서 꺼낼때 지금 갈 도로가 ..

백준 1068 링크 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다. www.acmicpc.net 문제 풀이 python 으로 풀었습니다. 끔찍한 실력 map[시작노드] 에 (도착노드)를 append 시켜주고 삭제될 노드를 입력 받은 후에 다시 삭제될 노드인 도착노드들을 다 없애줍니다. dfs로 탐색을 할 수 있도록 find() 함수로 탐색을 시작합니다. 만약 루트 노드가 삭제됬다면 탐색을 하지 않고 끝냅니다. 코드 def ..