python

[BaekJoon Online Judge] 2606 – 바이러스 문제 https://www.acmicpc.net/problem/2606 소스코드 dfs 를 이용해서 문제를 해결한다. 양방향 간선으로 표현된 네트워크 입력을 그래프로 표현한 뒤 1번 컴퓨터부터 탐색을 시작하면 바이러스에 감염되는 모든 컴퓨터를 찾아낼 수 있다. N = int(input()) V = int(input()) graph = [[0 for _ in range(N)] for _ in range(N)] for i in range(V): a,b […]

[BaekJoon Online Judge] 2667 – 단지번호붙이기 문제 https://www.acmicpc.net/problem/2667 소스코드 지도 내의 모든 좌표를 탐색하여, 집이 발견될 때마다 그 집의 좌표부터 dfs를 이용해 연결된 집을 모두 찾는다. 계속해서 앞의 과정을 반복하는데 단지 번호만 하나씩 늘려주기만 하면 해결할 수 있다. dx=[0,1,0,-1] dy=[1,0,-1,0] N = int(input()) town = [list(map(int,list(input()))) for _ in range(N)] district = 1 cnts,stack = […]

[BaekJoon Online Judge] 7569 – 토마토 문제 https://www.acmicpc.net/problem/7576 소스코드 7576 문제에서 공간 차원이 하나 늘어난 문제. 7576 문제와 마찬가지로 bfs를 이용한 최단거리 문제로 해결할 수 있다. from collections import deque dx = [0,1,0,-1,0,0] dy = [1,0,-1,0,0,0] dz = [0,0,0,0,-1,1] M,N,H = map(int,input().split()) field = [[list(map(int,input().split())) for _ in range(N)] for _ in range(H)] visit = […]

[BaekJoon Online Judge] 7576 – 토마토 문제 https://www.acmicpc.net/problem/7576 소스코드 bfs를 이용한 최단거리 문제로 해결할 수 있다. 익은 토마토 옆이면 그 다음 사이클에 익은 상태로 바뀌기 때문에, 초기 상태에 익은 토마토 모두를 q에 넣은 뒤 bfs 탐색을 시작한다. 탐색이 끝나면 visit 배열에서 가장 높은 숫자가 상자 내의 모든 토마토가 익는 최소 날짜가 된다. from collections import […]

[BaekJoon Online Judge] 12100 – 2048 (Easy) 문제 https://www.acmicpc.net/problem/12100 소스코드 문제에서 최대 다섯 번의 방향 전환이 가능하다고 제약을 걸었기 때문에, 5중 루프를 돌려서 가능한 모든 경우의 수를 만들었다. 앞서 만든 경우에 수에 대해, 문제에서 설명한 2048 게임룰(방향 전환에 따라 블록이 합쳐지는 조건)을 노가다로 작성해서 문제를 해결할 수 있었다. from copy import deepcopy def game(direction): global […]

[BaekJoon Online Judge] 13458 – 시험 감독 문제 https://www.acmicpc.net/problem/13458 소스코드 총 감독관은 오직 1명만 있어야 하므로, 총 감독관 한 명이 감당할 수 있는 인원을 초과한 인원에 대해서 필요한 부감독관 수를 산정하면 되는데 if – else 만으로 구현하니 시간초과가 나서, elif 조건을 하나 더 추가해서, d[] 배열에 메모이제이션 한 결과를 리턴할 수 있도록 했다. N = […]