https://www.acmicpc.net/problem/1726 처음에 최단경로를 구할 때 코드트리 메두사 문제처럼 최단경로를 미리 저장해 놓고 따라가는 방식으로 구현하려고 했다. 그래서 해당 코드를 바로 구현했는데 구현하자마자 반례가 생각났다.이 문제는 방향까지 고려해야 하기 때문에 단순히 최단거리라고 해서 최단시간이 되지는 않는다. 또한, 한 번에 3칸씩 갈 수 있기 때문에 단순히 한 칸 한 칸씩 최단거리를 구하는 건 무의미하다. 그래서 방향까지 고려해서 bfs를 돌려주었다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import j..
https://www.acmicpc.net/problem/1461 스터디원이 추천해 줘서 알게 된 전형적인 그리디 문제이다.처음 접근할 때는 가장 작은 음수값과 가장 큰 양수값을 미리 빼놓고 거리 계산에 미포함시키려고 했는데 이 경우는 항상 최적의 답이 안 나온다. 그 이유는 편도로 가는 길에 M개의 책을 놓을 수 있는데, 편도로 가면 무조건 한 개만 놓을 수 있다고 잘못 생각했기 때문이다..그리디 문제인 것만 눈치채면 정렬과 분기처리로 어렵지 않게 풀 수 있다.import java.io.*;import java.util.*;public class Main { static int N, M; static PriorityQueue minus; static PriorityQueue plus; static in..
https://www.acmicpc.net/problem/20061저처럼 푸시면 안됩니다.. 정답 코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;class Main { static int N; static int t, x, y; static int score = 0; static boolean[][] board = new boolean[10][10]; public static void main(String args[]) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.i..
https://www.acmicpc.net/problem/19237 정답 코드import java.awt.Point;import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.HashMap;import java.util.Map.Entry;import java.util.PriorityQueue;import java.util.StringTokenizer;public class Main { static int N, M, K; static int[][][] board; static int[][][] direction; static int[][] sharks; static boo..
https://www.acmicpc.net/problem/17472 다리 만들기 1은 어렵지 않게 풀었는데 다리 만들기 2는 MST 지식이 필요해서 좀 더 공부한 후 풀었다. 크루스칼 알고리즘이나 프림 알고리즘을 사용하면 풀 수 있다. 또한 섬의 개수가 최대 6개로 매우 작기 때문에 시간 초과 걱정 없이 알고리즘 공부할 수 있는 문제였다. import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.List;import java.util.Queue;import java.util.StringTokenizer;public clas..
https://www.acmicpc.net/problem/17837 import sysinput = sys.stdin.readlinedi = [0, 1, 0, -1]dj = [1, 0, -1, 0]def setting(d): if d == 1: # 우 return 0 elif d == 2: # 좌 return 2 elif d == 3: # 상 return 3 else: return 1 def move(): global n for number in range(1, k+1): num, si, sj, d = mal[number] # 1. 해당 위치에 있는 말들 중, 본..
https://www.acmicpc.net/problem/2146 초기 구현에는1. 육지인 영역 찾기2. 바다와 인접한 영역만 골라내기3. bfs 탐색 위 메서드를 모두 구현했는데 2번 메서드가 없어도 정답일 것 같아 삭제했더니 역시 정답이었다. 근데 지금 생각해 보면 1번이랑 2번을 합쳐서 구현했으면 훨씬 메모리 측면에서 효율적일 것 같다는 생각이 든다.ㅎ 정답 코드import sysfrom collections import dequeinput = sys.stdin.readlinen = int(input())board = [list(map(int, input().split())) for _ in range(n)]number = [[0 for _ in range(n)] for _ in range(n)]..
https://www.acmicpc.net/problem/7576 이제 토마토는 마스터했다고 생각했는데 아니었다 ㅎ모든 위치에 토마토가 있는 경우를 고려 안 해서 틀렸지만 그 부분만 고치니 바로 풀렸다.놓치는 예외상황이 너무 많아서 걱정이다.. import sysfrom collections import dequeinput = sys.stdin.readlinem, n = map(int, input().split())board = [list(map(int, input().split())) for _ in range(n)]tomatos = deque()for i in range(n): for j in range(m): if board[i][j] == 1: tomatos...
