[BOJ] - Python (45) 썸네일형 리스트형 [백준] 16928 : 뱀과 사다리 게임 python 1. 사다리와 뱀을 만나면 무조건 이동한다. 2. 사다리와 뱀이 있는 칸은 여러 번 방문할 수도 있으니, 주사위 던진 횟수가 최소가 되게 신경써야 한다. 이 두 가지만 신경쓰면 크게 어렵지 않은 문제였다. from collections import deque import sys input = sys.stdin.readline def bfs(start): q = deque() # 시작점을 큐에 넣고 방문체크 q.append(start) visited[start] = True while q: # 현재 위치를 cur에 저장 cur = q.popleft() # 주사위를 굴려서 갈 수 있는 곳을 확인함 for i in range(1,7): ncur = cur+i # 100번 칸에 도달했다면 주사위 던진 횟수를+1.. [백준] 1012 : 유기농 배추 python 배추들이 상하좌우로 인접해있는 곳에는 배추흰지렁이가 한 마리만 있어도 되기 때문에 모든 배추들이 탐색완료가 될 때까지 BFS나 DFS를 수행하고 그 횟수를 세주면 되는 간단한 문제다. 평소엔 행을 x로 열을 y로 두고 푸는 경우가 많은데 이 문제에선 반대라서 그게 좀 헷갈렸다. from collections import deque import sys input = sys.stdin.readline def bfs(ay,bx): q = deque() q.append((ay,bx)) visited[ay][bx] = True while q: y,x = q.popleft() for i in range(4): ny = y+dy[i] nx = x+dx[i] if 0 [백준] 12015 : 가장 긴 증가하는 부분 수열 2 python https://velog.io/@ledcost/%EB%B0%B1%EC%A4%80-12015-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-2-%EA%B3%A8%EB%93%9C2-%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89 위 포스트를 참고해서 문제를 풀었다. 우선 arr라는 리스트에 입력받은 값들을 저장한다. 그리고 res라는 리스트를 만들고 arr[0]를 저장한 뒤에, arr에 저장된 값과 res의 마지막값을 비교하며 더 클 경우에는 res에 추가하고 작거나 같을 경우에는 res안에서 적절한 .. [백준] 2110 : 공유기 설치 python 이분탐색 문제들은 어떤 값을 이분탐색할 것인지 결정하는 게 가장 어려운 것 같다... 이 문제는 공유기 사이의 거리값으로 이분탐색을 해서 풀어야 하는 문제였다. # 집의 개수와 공유기의 개수를 입력받음 n,c= map(int,input().split()) # 집의 좌표들을 입력받고 정렬한 리스트 house를 생성 house = sorted([int(input()) for _ in range(n)]) # 공유기 사이의 거리값들을 이분탐색 하는 것이기 때문에 # 최소거리인 1과 최대거리인 house[-1]-house[0]을 start와 end로 지정함 start,end = 1, house[-1]-house[0] # 인접한 공유기의 거리의 최대값을 저장할 변수 answer = 0 # 이분탐색이 가능할 동안 반.. [백준] 10816 : 숫자 카드 2 python N개의 카드를 오름차순으로 정렬한 리스트 card에서 bisect라이브러리의 내장함수인 bisect_right와 bisect_left를 이용해서 각각의 숫자가 몇개씩 있는지 세고, 딕셔너리에 추가한 뒤 출력하는 방식을 생각했는데 자꾸 시간초과가 나왔다. bisect_right(list, value)는 list에서 value가 들어갈 가장 오른쪽 위치를 알려주고 bisect_left(list, value)는 왼쪽 위치를 알려줘서 정렬된 list에 사용하면 오른쪽위치-왼쪽위치=list내에서 그 숫자의 개수가 된다. 그런데 생각해보니 굳이 다시 저장하고 끄집어낼 필요가 없는 거다. 그래서 딕셔너리를 쓰지 않고 그냥 바로 출력해버리니까 정답판정을 받았다. import bisect n = int(input()) .. [백준] 17086 : 아기 상어 2 python 그래프를 입력받을 때 상어가 있는 위치의 행,열 위치를 큐에 삽입한다. 큐에서 상어의 위치를 하나씩 꺼내면서 주변에 0(아직 탐색하지 않은 물)이 있으면 거리값을 1 증가시키고 그걸 그래프에 저장한 뒤 BFS 탐색을 하는 식으로 문제를 풀었다. from collections import deque import sys input = sys.stdin.readline def bfs(): while shark: x,y = shark.popleft() for i in range(8): nx = x+dx[i] ny = y+dy[i] if 0 [백준] 1743 : 음식물 피하기 python NxM 크기의 그래프를 만들고 음식물쓰레기가 있는 자리는 1로 표시한다. 그리고 그래프에서 아직 미방문이면서 음식물쓰레기가 있는 자리에서부터 BFS나 DFS를 수행하면서 쓰레기의 크기를 cnt_list에 추가해줬다. 모든 탐색이 끝나고나서 max(cnt_list)를 출력해주면 된다. from collections import deque import sys input = sys.stdin.readline def bfs(a,b): q = deque() q.append((a,b)) visited[a][b] = 1 cnt = 1 while q: x,y = q.popleft() for i in range(4): nx = x+dx[i] ny = y+dy[i] # 미방문이면서 음식물쓰레기가 있는 자리라면 큐에 넣고 .. [백준] 7562 : 나이트의 이동 python from collections import deque import sys input = sys.stdin.readline def bfs(a,b): q = deque() q.append((a,b)) while q: x,y = q.popleft() if x==d_x and y==d_y: # 목적지까지의 이동횟수 출력 return board[x][y] for i in range(8): nx,ny = x+dx[i],y+dy[i] # 이동할 수 있다면 board에 이동횟수를 기록하고, 큐에 넣음 if 0 이전 1 2 3 4 5 6 다음
