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...
https://www.acmicpc.net/problem/1600 처음에 말처럼 이동하는 경우와 아닌 경우를 동시에 queue에 넣어서 돌렸고 문제 예제도 맞았다. 근데 제출하니까 틀려서 뭐가 문제지 하고 생각해 보니 말처럼 이동하면 안 되는 경우에 말처럼 이동한 후 visited를 True로 바꿔버려서 다른 경우를 고려하지 못하는 문제가 발생했다. 이 예외 상황을 처리하기 위해 2차원으로 관리하던 배열을 3차원으로 바꿨고, 그중 마지막 차원은 말처럼 이동한 횟수로 두었다. 문제가 조금 익숙하다고 느껴졌는데 2024 하반기 삼성 계열사 오후 2번 문제랑 결이 비슷하다.. 그 문제도 3차원으로 이동을 관리해야 해서 비슷하게 느껴졌다. 정답코드import sysfrom collections import d..
https://www.acmicpc.net/problem/2667 import sysfrom collections import dequeinput = sys.stdin.readlinen = int(input())board = [list(map(int, input().strip())) for _ in range(n)]is_home = []for i in range(n): for j in range(n): if board[i][j] == 1: is_home.append((i, j)) di = [0, 1, 0, -1]dj = [1, 0, -1, 0]def bfs(si, sj): global visited count = 1 dq = de..
레벨 순서 탐색: BFS는 시작점에서 가까운 노드부터 탐색하므로, 먼저 방문한 경로가 항상 가장 짧다.거리 기록 방식: 코드에서 distance[ni][nj]를 처음 갱신하는 순간이 바로 해당 칸에 도달하는 최단거리다. 이후 같은 칸을 다시 방문하지 않으므로 min 함수로 비교할 필요가 없다.큐의 순서: BFS에서 큐에 넣는 순서는 거리가 증가하는 순서이다. 따라서 특정 칸을 가장 처음 방문할 때의 거리가 최단거리임을 보장한다. 단, 위 경우는 가중치가 동일할 때의 얘기다. 가중치가 다를 때는 min 함수 또는 다익스트라를 활용해야 한다.
https://www.codetree.ai/training-field/frequent-problems/problems/artistry/ 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 90도 회전하는 원리를 아직도 헷갈려한다.. 큰일이다..예술성 구하는 로직은 30분도 안 걸렸는데 회전 로직만 2시간 넘게 걸렸다... from collections import dequeimport collectionsn = int(input())board = [list(map(int, input().split())) for _ in range(n)]# 상하좌우로 인접해..
