본문 바로가기

전체 글

(261)
[백준] 9205 : 맥주 마시면서 걸어가기 python 현 위치에서 바로 행사장까지 갈 수 있다면 happy를 출력하고, 그렇지 않으면 갈 수 있는 편의점이 있는지 찾아본다. 있다면 그 편의점에서 맥주를 충전하고 위 과정을 반복한다. 모든 편의점을 들렀는데도 행사장까지 갈 수 없다면 sad를 출력하면 된다. import sys from collections import deque input = sys.stdin.readline # 두 좌표 사이의 거리를 구하는 함수 def dist(ax,ay,bx,by): return abs(ax-bx)+abs(ay-by) def bfs(start,fest,conv): queue = deque() # 시작점을 큐에 넣음 queue.append((start[0],start[1])) # 편의점 방문체크를 위한 리스트 visite..
[백준] 14503 : 로봇 청소기 python 바라보는 방향을 유지한 채로 후진하는 것을 제대로 확인하지 못해서 계속 오답이 나왔다. 그렇게 어려운 문제는 아닌 것 같은데 왜 막상 풀면 잘 안 풀리는 건지..아직 연습이 많이 부족한 듯 from collections import deque import sys input = sys.stdin.readline dx = [-1,0,1,0] dy = [0,1,0,-1] n, m = map(int,input().split()) r,c,d = map(int,input().split()) graph = [] visited = [[False for j in range(m)]for i in range(n)] for i in range(n): graph.append(list(map(int,input().split())..
[백준] 2468 : 안전 영역 python 오타를 찾느라 고생을 좀 했다... import sys from collections import deque input = sys.stdin.readline n = int(input()) graph = [] for i in range(n): graph.append(list(map(int,input().split()))) # 최대 높이를 변수에 저장 max_height = max(map(max,graph)) dx = [-1,1,0,0] dy = [0,0,-1,1] def bfs(graph,visited,x,y,h): queue = deque() queue.append((x,y)) visited[x][y] = True while queue: a,b = queue.popleft() for i in range(..
[백준] 1525 : 퍼즐 python BFS를 쓰면 될 것 같다는 생각은 했지만 어떻게 풀어야 할지 감이 오질 않아서...결국 서치해보고 풀었다. 3x3표라고 해서 2차원 리스트를 고집하지 말고 문자열로 바꿔서 풀 것. 그리고 딕셔너리를 만들어서 변화하는 퍼즐의 상태와, 그 상태가 만들어지는 데까지 필요한 이동 횟수를 저장하는 것이 핵심이었다. from collections import deque target = "" for i in range(3): # 빈 칸을 지우고 이어붙이기 target += input().replace(' ','') # key: 각 퍼즐의 상태를 문자열로 만든 것 # value: 그 상태에 도달하는 데에 필요한 이동 횟수 visited = dict() # 초기상태가 되기 위한 이동횟수는 0 visited[target..
[백준] 10451 : 순열 사이클 python 1. T를 입력받는다. 2. 다음 과정을 T번 반복한다. 2-1. 정점의 개수 N을 입력받는다. 2-2. [n+1][] 크기의 리스트 graph를 생성한다. 2-3. data라는 리스트에 연결 정보를 저장한다. 2-4. 1부터 N+1까지 반복하면서 그래프에 연결 정보를 추가한다. 2-5. 방문 여부 확인을 위한 리스트 visited와 순열 사이클의 개수를 카운트 하기 위한 cnt를 초기화한다. 2-6. N개의 정점에 대해, 해당 정점을 아직 방문하지 않았다면 DFS를 수행하고 cnt를 1 증가시킨다. 2-7. cnt를 출력한다. 3. DFS 함수를 구현한다. import sys input = sys.stdin.readline t = int(input()) def dfs(v): visited[v] = Tr..
[백준] 11724 : 연결 요소의 개수 python 그래프에 연결 요소가 총 몇 개 있는지 카운트하는 문제다. 즉 그래프에서 모든 정점을 다 방문할 때까지 DFS나 BFS로 탐색한 횟수를 세면 된다. DFS를 사용해서 풀었는데 RecursionError가 발생해서 인위적으로 재귀횟수를 늘리는 코드를 추가했다. sys.setrecursionlimit(10**6) import sys input=sys.stdin.readline sys.setrecursionlimit(10**6) n,m=map(int,input().split()) cnt=0 visited = [False]*(n+1) graph=[[]for i in range(n+1)] for i in range(m): s,e = map(int,input().split()) graph[s].append(e) g..
[백준] 2644 : 촌수계산 python 전에 풀었던 케빈 베이컨의 6단계 법칙 문제에서 사용했던 방법을 그대로 썼다. 모든 정점에 대해 bfs를 수행할 필요는 없고, 촌수를 계산해야 하는 번호에 대해서만 bfs를 수행해주면 된다. import sys from collections import deque input = sys.stdin.readline n = int(input()) a,b=map(int,input().split()) m=int(input()) graph = [[]for i in range(n+1)] result = [] for i in range(m): s,e = map(int,input().split()) graph[s].append(e) graph[e].append(s) def bfs(start): visited = [Fal..
[백준] 1389 : 케빈 베이컨의 6단계 법칙 python n개의 정점에 대해 bfs를 수행할 때마다 num이라는 배열에 연관된 정점사이의 거리를 기록하고, num의 총합을 result라는 리스트에 append해준다. 1-3, 3-2, 2-4, 4-5이렇게 연결되어있을 때 1번을 시작 정점으로 bfs를 수행하면서 1번의 인접정점인 3,4의 거리가 1이라는 것을 num[3], num[4]에 기록해준다. 그리고 3번을 시작 정점으로 다시 bfs를 수행할 때 3번의 인접 정점인 2번자리 num[2]에는 num[3]+1을 저장하는 방식으로 하면 1번과 연관이 있는 각 정점간의 거리를 알 수 있다. import sys from collections import deque input = sys.stdin.readline n,m = map(int,input().split()..