문제 https://www.acmicpc.net/problem/4195 풀이 전형적인 Union-Find 문제이지만, 각 원소들이 정수가 아닌 문자열로 구성되어 있는 특징이 있다. 정수를 문자열로 대응시키는 것은 Dictionary를 쓰면 쉽게 할 수 있으므로 다음과 같은 방식으로 알고리즘이 진행된다 입력값(문자열 2개)에 대해 각 문자열이 Dictionary에 대응되는 Value가 있는지 판단한다. 1에서 없다면 Dictionary에 [String:Integer] 꼴로 매핑한다. 있다면 그냥 넘어간다. 매핑이 끝났다면, 들어온 두 문자열로 union(a, b) 연산을 하고 그 집합 내부의 원소의 개수를 카운트한다. 여기서 문제는 3번이다. 어떻게 해야 효율적으로 집합 내부의 원소를 카운트 할 수 있을까? ...
문제 https://www.acmicpc.net/problem/1726 풀이 로봇이 바라보는 방향에 따라서 갈 수 있는 노드가 달라진다 -> 3차원 그래프다 (세로 m, 가로 n, 높이가 4인) 이 발상만 빠르게 해낸다면 평범한 BFS 문제가 된다. 하나의 노드에서 최대 5개의 노드와 연결이 가능하다(회전 2방향, 전진 3방향) 하지만 2칸 이상 전진했을때, 앞선 칸이 1이면 넘어가지 못한다. (점프를 할 수 없다) 이것만 주의하고 BFS 탐색을 하면 쉽게 결과를 낼 수 있다. 코드 # east 0 west 1 south 2 north 3 from collections import deque def bfs(start): bfsQ = deque() bfsQ.append(start) isVisited[start[0]][start[1]][start[2]] = True count[start[0]][start[1]][start[2]] = 0 while(bfsQ): node = bfsQ.popleft() currentDir = node[2] currentCount = count[node[0]][node[1]][node[2]] if node == end: return currentCount for dir in rotate[currentDir]: if end == [node[0], node[1], dir]: return currentCount + 1 if isVisited[node[0]][node[1]][dir]: continue isVisited[node[0]][node[1]][dir] = True count[node[0]][node[1]][dir] = currentCount + 1 bfsQ.append((node[0], node[1], dir)) if currentDir == 0: moves = [(0, 1), (0, 2), (0, 3)] elif currentDir == 1: moves = [(0, -1), (0, -2), (0, -3)] elif currentDir == 2: moves = [(1, 0), (2, 0), (3, 0)] else: moves = [(-1, 0), (-2, 0), (-3, 0)] for move in moves: row = node[0] + move[0] column = node[1] + move[1] if end == [row, column, currentDir]: return currentCount + 1 if row < 0 or row >= m or column < 0 or column >= n: continue if isVisited[row][column][currentDir]: continue if graph[row][column] == 1: break isVisited[row][column][currentDir] = True count[row][column][currentDir] = currentCount + 1 bfsQ.append((row, column, currentDir)) graph = [] rotate = {0: [2, 3], 1: [2, 3], 2: [0, 1], 3: [0, 1]} m, n = map(int, input().split()) for _ in range(m): graph.append(list(map(int, input().split()))) start = list(map(int, input().split())) end = list(map(int, input().split())) for i in range(3): start[i] -= 1 end[i] -= 1 isVisited = [[[False] * 4 for i in range(n)] for j in range(m)] count = [[[0] * 4 for i in range(n)] for j in range(m)] print(bfs(start))
문제 https://www.acmicpc.net/problem/3055 풀이 입력으로 그래프가 주어지고, 어느 칸에서 BFS를 시작해야하는지 알려준다. 문제를 읽어보면 고슴도치와 물 둘 다 BFS 탐색을 해야 하는 것을 알 수 있다. 주의할 점은 예제에는 초기에 물인 칸이 1개밖에 없지만 문제를 읽어보면 1칸이라는 제약조건이 없다. 따라서 물이 여러칸일 때도 생각하고 프로그래밍을 해야 한다. 처음에 두 가지 생각을 했다. BFS탐색을 각각 따로 하는 방법 고슴도치를 먼저 BFS 탐색시켜서 그래프에 각 칸마다 몇번째 이동에 도달하는지 검사한다. 다음에 물을 BFS 탐색해서 1의 결과가 가능한지를 판단한다. 고슴도치와 물을 단계별로 번갈아가면서 BFS 탐색 하는 방법 ...
문제 https://www.acmicpc.net/problem/7576 풀이 처음엔 무난한 BFS 문제라고 생각했다. 처음부터 익어있는 토마토(루트 토마토라고 하겠다.)가 들어있는 칸을 알아낸 다음에 반복문으로 BFS를 적용하고, 루트 토마토를 할 때마다 만약 칸에 더 적은 숫자가 들어 갈 수 있다면 숫자를 업데이트 하는 식으로 문제를 풀었다. 그랬더니 시간초과가 나온다. 쓸데없는 연산이 너무 많아서 그렇다. 정확한 풀이는 BFS 큐를 처음 만들때부터 모든 루트 토마토를 넣어서 초기화 하는 것이었다. 그러면 모든 루트 토마토를 기준으로 동시에 탐색할 수 있으니까. 칸을 탐색할때도 더 높은 숫자가 나오면 그 칸은 큐에 넣을 필요가 없다. 이미 전에 했던 탐색이 더 좋은 결과를 가져다 주었을태니 ...
문제 https://www.acmicpc.net/problem/2667 풀이 그래프가 입력으로 주어지고, 각 노드마다 탐색의 범위가 상하좌우로 제한된다. 앞서 해결했던 미로 탐색과 순열 사이클을 섞어놓은 듯 한 문제이다. 따라서 다음과 같은 과정으로 출력값을 얻었다. 전체 그래프를 탐색하는 2중 반복문을 작성한다. 방문하지 않은 노드가 나올 때마다 그래프 탐색(DFS, BFS)를 실시한다. 각 그래프를 탐색했을때 노드의 개수를 저장하고 정렬한 다음에 출력한다. 코드 from collections import deque def bfs(v): bfsQ = deque() bfsQ.append(v) isVisited[v[0]][v[1]] = True moves = [(1, 0), (-1, 0), (0, 1), (0, -1)] count = 1 while bfsQ: node = bfsQ.popleft() for move in moves: row = node[0] + move[0] column = node[1] + move[1] if row < 0 or row >= n or column < 0 or column >= n: continue if graph[row][column] != 0 and not isVisited[row][column]: isVisited[row][column] = True bfsQ.append((row, column)) count += 1 return count n = int(input()) graph = [] for _ in range(n): temp = input() graph.append(list(map(int, temp))) isVisited = [[False] * n for i in range(n)] area = [] for row in range(n): for column in range(n): if graph[row][column] == 1 and not isVisited[row][column]: area.append(bfs((row, column))) area.sort() print(len(area)) for i in range(len(area)): print(area[i])
문제 https://www.acmicpc.net/problem/2331 풀이 수열을 만드는 반복문을 만든다. 도중에 기존에 있는 원소와 같은 원소가 나오면 반복문을 종료한다. 처음으로 나온 같은 원소의 인덱스를 출력한다. (인덱스는 0부터 시작이기에 더하고 뺄 필요가 없다.) 너무 간단하게 풀렸는데 시간복잡도가 별로 좋아보이진 않는다. 더 좋은 방법이 있을듯 싶다. 코드 a, p = map(int, input().split()) seq = [a] while True: element = 0 for i in str(seq[-1]): element += (int(i) ** p) if element in seq: break seq.append(element) print(seq.index(element))
문제 https://www.acmicpc.net/problem/1697 풀이 입력으로 수빈이와 동생의 위치, 그리고 수빈이가 이동할 수 있는 제약조건을 알려준다. 수빈이의 위치보다 동생의 위치가 더 앞에 있거나 같을때는 (n >= k) 뒤로 가는 방법이 한칸 이동하는 것 밖에 없으므로 n - k 로 쉽게 결과를 도출 할 수 있다. 그 외의 경우에는 각각의 좌표를 노드라고 생각했을 때, 이 그래프는 각 노드가 노드값이 1만큼 크거나 작은 노드와 2배인 노드와 연결되어 있다. 따라서 BFS를 이용하면 쉽게 해결 할 수 있다. ...
문제 https://www.acmicpc.net/problem/2178 풀이 입력값으로 미로의 크기와 구성이 주어진다. 미로 안에서는 값이 1인 칸으로만 이동 할 수 있고, 또 각 칸에서는 상하좌우의 칸으로밖에 이동하지 못한다. -> 현재 칸에서 상하좌우의 칸을 탐색해서 1인 경우에만 Queue에 넣는다. 이 문제에서는 각 노드를 방문했는지의 여부보다 몇번째에 방문했는지의 여부가 더 중요하다. -> 이전 노드의 방문 순서에 1을 더한 값을 현재 노드의 방문 순서로 한다. (isVisited가 Bool이 아닌 Integer로 구현된다) 이렇게 얻어낸 두가지 인사이트로 BFS를 구현한다. 코드 from collections import deque def bfs(location): visit = [[0] * m for _ in range(n)] bfsQ = deque() bfsQ.append(location) visit[0][0] = 1 while bfsQ: node = bfsQ.popleft() up = [node[0] - 1, node[1]] down = [node[0] + 1, node[1]] left = [node[0], node[1] - 1] right = [node[0], node[1] + 1] moves = [up, down, left, right] for i in range(len(moves)): x = moves[i][0] y = moves[i][1] if x < 0 or y < 0 or x >= n or y >= m: continue if maze[x][y] == "0": continue if visit[x][y] == 0: visit[x][y] = visit[node[0]][node[1]] + 1 bfsQ.append([x, y]) return visit[n - 1][m - 1] maze = [] n, m = map(int, input().split()) for i in range(n): temp = list(input()) maze.append(temp) print(bfs([0, 0])) 시작 노드와 종료 노드가 명확하게 정해져 있으므로 DFS로도 풀릴것이라는 생각이 든다.
문제 https://www.acmicpc.net/problem/1260 풀이 심플하다. 입력값으로 그래프가 주어지고, DFS와 BFS를 이용해 탐색한 결과를 각각 출력하면 된다. 코드 from collections import deque def dfs(v, dfsArray): isVisitedDFS[v] = True dfsArray.append(v) for i in range(len(graph[v])): if graph[v][i] != 0 and isVisitedDFS[i] == False: dfs(i, dfsArray) def bfs(v, bfsArray): QueueBFS = deque() isVisitedBFS[v] = True QueueBFS.append(v) while len(QueueBFS) != 0: node = QueueBFS.popleft() bfsArray.append(node) for i in range(len(graph[node])): if graph[node][i] != 0 and not isVisitedBFS[i] QueueBFS.append(i) isVisitedBFS[i] = True n, m, v = map(int, input().split()) graph = [[0] * (n + 1) for i in range(n + 1)] isVisitedDFS = [False for i in range(n + 1)] isVisitedBFS = [False for i in range(n + 1)] dfsArray = [] bfsArray = [] for i in range(m): a, b = map(int, input().split()) graph[a][b] = graph[b][a] = 1 dfs(v, dfsArray) bfs(v, bfsArray) for node in dfsArray: print(node, end=" ") print() for node in bfsArray: print(node, end=" ") print()
문제 https://www.acmicpc.net/problem/10451 풀이 순열이 각각의 (1부터 시작하는)인덱스와 매칭되어있는 그래프를 만들면 쉽게 해결된다. (친절하게 문제에 그림도 있다.) 순열과 인덱스는 내부 원소들이 순서를 제외하고 같으므로 무조건 내부에 사이클을 형성하게 된다. 따라서 문제에서 주어진 그대로 우리는 서로 가르키는 방향을 재귀로 따라가고, 이미 방문한 숫자가 나온다면 재귀를 종료시키기를 반복해서 생기는 사이클의 총 개수를 카운트 하기만 하면 된다. 코드 def dfs(v, start): isVisited[v] = True if not isVisited[permutation[v - 1]]: dfs(permutation[v - 1], start) n = [] per = [] t = int(input()) for _ in range(t): n_temp = int(input()) per_temp = list(map(int, input().split())) n.append(n_temp) per.append(per_temp) for case in range(t): count = 0 isVisited = [False] * (n[case] + 1) permutation = per[case] for i in range(1, n[case] + 1): if not isVisited[i]: dfs(i, i) count += 1 print(count) 굳이 재귀를 쓰지 않더라도 반복문만으로도 깔끔한 코드가 나올것 같다.