class Graph:
def __init__(self, n):
self.data = {}
for i in range(1, n + 1):
self.data[i] = set()
def add_edge(self, n, m):
self.data[n].add(m)
self.data[m].add(n)
def dfs(self, start):
visited = [False] * (len(self.data) + 1)
stack = []
stack.append(start)
while stack:
cur = stack.pop()
if not visited[cur]:
print(cur, end=" ")
visited[cur] = True
temp = []
for i in self.data[cur]:
if not visited[i]:
temp.append(i)
temp.sort()
temp.reverse()
stack.extend(temp)
def bfs(self, start):
import collections
visited = [False] * (len(self.data) + 1)
queue = collections.deque()
queue.append(start)
while queue:
cur = queue.popleft()
if not visited[cur]:
print(cur, end=' ')
visited[cur] = True
temp = []
for i in self.data[cur]:
if not visited[i]:
temp.append(i)
temp.sort()
queue.extend(temp)
from sys import stdin
node_edge_start = list(map(int, stdin.readline().split()))
graph = Graph(node_edge_start[0])
li = []
for i in range(0, node_edge_start[1]):
rawInput = list(map(int, stdin.readline().split()))
graph.add_edge(rawInput[0], rawInput[1])
graph.dfs(node_edge_start[2])
print()
graph.bfs(node_edge_start[2])
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
ArrayList list = new ArrayList<>();
for (int i = 0; i < n; i++) {
list.add(in.nextInt());
}
int[][] arr = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(i < j)
continue;
if(i == j)
arr[i][j] = list.get(j);
else {
arr[i][j] = arr[i-1][j] + list.get(i);
}
}
}
int max = arr[0][0];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(i < j) continue;
if (arr[i][j] > max) {
max = arr[i][j];
}
}
}
System.out.println(max);
}
}
이렇게 제출했더니 메모리 초과가 났다.
그래서 아 동적계획법은 생각보다 메모리를 아껴쓸 수가 있지? 하고
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] list = new int[n];
for (int i = 0; i < n; i++) {
list[i] = in.nextInt();
}
int[] arr = new int[n];
int max = list[0];
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if (i == j) arr[j] = list[i];
else arr[j] = arr[j - 1] + list[j];
if(arr[j] > max) max = arr[j];
}
}
System.out.println(max);
}
}
import java.util.Scanner;
public class Main {
static int count = 0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] col = new int[n];
queen(col, n, 0);
System.out.println(count);
}
static void queen(int[] col, int n, int num) {
if (num == n) {
count++;
return;
}
for (int i = 0; i < n; i++) {
if (promising(col, num, i)) {
col[num] = i;
queen(col, n, num + 1);
col[num] = 0;
}
}
}
static boolean promising(int[] col, int r, int c) {
for (int i = 0; i < r; i++) {
if(col[i] == c || Math.abs(c - col[i]) == Math.abs(r - i)) {
return false;
}
}
return true;
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = "";
StringBuilder sb = new StringBuilder();
try {
s = br.readLine();
} catch (IOException e) {}
StringTokenizer st = new StringTokenizer(s);
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[] result = new int[m];
permutationWithRepetition(n, m, 0, result, sb);
System.out.println(sb);
}
static void permutationWithRepetition(int n, int m, int num, int[] result, StringBuilder sb) {
if (num == m) {
for (int i = 0; i < m; i++) {
sb.append(result[i] + " ");
}
sb.append("\n");
return;
}
for (int i = 0; i < n; i++) {
if(num != 0 && result[num - 1] > i + 1)
continue;
else {
result[num] = i + 1;
permutationWithRepetition(n, m, num + 1, result, sb);
}
}
}
}
N과 M (1), N과 M (2)를 쉽게 풀었기 때문에 N과 M (3)을 보자마자 이건 더 쉬운데? 했다.
중복순열이기 때문에 boolean 타입의 visited[n] 배열을 따로 유지할 필요가 없어서 코드도 더 짧고 더 쉬웠다.
15649번 코드에서 visited 관련된 코드만 삭제한 코드인
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[] result = new int[m];
permutationWithRepetition(n, m, 0, result);
}
static void permutationWithRepetition(int n, int m, int num, int[] result) {
if (num == m) {
for (int i = 0; i < m; i++) {
System.out.print(result[i] + " ");
}
System.out.println();
return;
}
for (int i = 0; i < n; i++) {
result[num] = i + 1;
permutationWithRepetition(n, m, num + 1, result);
}
}
}
이렇게 제출했다.
그랬더니
시간초과가 났다.
그래서 이렇게 해봤는데
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[] result = new int[m];
for(int i = 0; i < Math.pow(n, m); i++) {
for (int j = 0; j < m; j++) {
System.out.print((int)(i / Math.pow(n, m - j - 1)) % n + 1 + " ");
}
System.out.println();
}
}
}
이래도 시간초과가 났다.
그래서 동적계획법으로 해야하나 하고 정말 두 시간 동안 별 짓을 다 해봤다.
그런데도 계속 시간 초과가 나는거다.
내가 정답률 70% 짜리 문제에 이렇게 시간을 투자하고 있다는게 너무 어이없어서 결국 구글링을 해봤다.
그랬더니 시간 초과의 원인은 바로 입출력에 있었다.
내가 처음 짠 코드 그대로에 입출력만 다르게 했더니 성공했다.
StringBuilder와 String의 차이에 대한 글을 포스팅까지 했는데 써먹지를 않았고 지난학기 자바 응용 수업에서 입출력스트림을 그렇게 많이, 자세히 배웠는데도 써먹지를 않은 나를 반성하게 되었다.
처음 짰던 그 코드에서 입출력하는 부분만 바꿔서
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = "";
StringBuilder sb = new StringBuilder();
try {
s = br.readLine();
} catch (IOException e) {}
StringTokenizer st = new StringTokenizer(s);
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[] result = new int[m];
permutationWithRepetition(n, m, 0, result, sb);
System.out.println(sb);
}
static void permutationWithRepetition(int n, int m, int num, int[] result, StringBuilder sb) {
if (num == m) {
for (int i = 0; i < m; i++) {
sb.append(result[i] + " ");
}
sb.append("\n");
return;
}
for (int i = 0; i < n; i++) {
result[num] = i + 1;
permutationWithRepetition(n, m, num + 1, result, sb);
}
}
}
이렇게 제출했더니 성공했다.
괜히 쓸데없이 2시간을 버린 것 같아서 약간 허탈하지만 덕분에 매우 중요한 것을 알게 되었다.
1. Scanner, System.out.print()보다 InputStreamReader를 쓰는게 더 빠르다.
2. 문자열에 계속 + " " 이런식으로 append할 일이 많으면 StringBuilder를 쓰는 게 훨씬 빠르다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
boolean[] visited = new boolean[n];
int[] result = new int[m];
combination(n, m, 0, visited, result);
}
static void combination(int n, int m, int num, boolean[] visited, int[] result) {
if (num == m) {
for (int i = 0; i < m; i++) {
System.out.print(result[i] + " ");
}
System.out.println();
}
else {
for (int i = 0; i < n; i++) {
if(!visited[i]) {
if(num != 0) {
if (result[num - 1] < i + 1) {
visited[i] = true;
result[num] = i + 1;
}
else continue;
}
else {
visited[i] = true;
result[num] = i + 1;
}
combination(n, m, num + 1, visited, result);
visited[i] = false;
}
}
}
}
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
boolean[] visited = new boolean[n];
int[] result = new int[m];
permutation(n, m, 0, visited, result);
}
static void permutation(int n, int m, int num, boolean[] visited, int[] result) {
if (num == m) {
for (int i = 0; i < m; i++) {
System.out.print(result[i] + " ");
}
System.out.println();
return;
}
for (int i = 0; i < n; i++) {
if(!visited[i]) {
visited[i] = true;
result[num] = i + 1;
permutation(n, m, num + 1, visited, result);
visited[i] = false;
}
}
}
}
순열을 구하는 방법을 모른다면 어려웠을 문제지만 순열을 공부했기 때문에 쉽게 풀 수 있었다.
7개월 뒤 8월 16일에 어떠한 것도 보지 않고 다시 풀어보았다. 이번엔 C++로 풀어봤다.
#include <vector>
#include <iostream>
using namespace std;
int n, m;
void permutation(int num, vector<bool> visited, vector<int> result) {
if (num == m) {
for (int i = 0; i < result.size(); i++) {
cout << result[i] << " ";
}
cout << '\n';
return;
}
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
result[num] = i;
visited[i] = true;
permutation(num + 1, visited, result);
visited[i] = false;
}
}
}
int main() {
cin >> n >> m;
vector<bool> visited(n + 1, false);
vector<int> result(m);
permutation(0, visited, result);
system("pause");
return 0;
}
import java.util.Scanner;
public class Combination {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
boolean[] visited = new boolean[n];
for (int i = 0; i < n; i++) {
visited[i] = false;
}
int[] result = new int[k];
combination(visited, n, k, 0, result);
}
static void combination(boolean[] visited, int n, int k, int num, int[] result) {
if (num == k) {
for (int i = 0; i < k; i++) {
System.out.print(result[i] + " ");
}
System.out.println();
return;
}
for (int i = 0; i < n; i++) {
if(!visited[i]) {
if (num > 0) {
if (result[num - 1] < i + 1) {
visited[i] = true;
result[num] = i + 1;
}
else continue;
}
else {
visited[i] = true;
result[num] = i + 1;
}
combination(visited, n, k, num + 1, result);
visited[i] = false;
}
}
}
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(); //1부터 n까지의 숫자 중에서
int r = in.nextInt(); //r개를 뽑는다
boolean[] visited = new boolean[n];
int[] selected = new int[r];
for (int i = 0; i < n; i++) {
visited[i] = false;
}
permutation(selected, visited, n, r, 0);
}
static void permutation(int[] selected, boolean[] visited, int n, int r, int num) {
if (num == r) {
for (int i = 0; i < r; i++) {
System.out.print(selected[i] + " ");
}
System.out.println();
return;
}
for (int i = 0; i < n; i++) {
if(!visited[i]){
visited[i] = true;
selected[num] = i + 1;
permutation(selected, visited, n, r, num + 1);
visited[i] = false;
}
}
}
}
permutation 함수의 매개변수인 num은 num번째 숫자를 정하는 것이다.
permutation 함수의 for문은 그 num번째 자리에 1부터 n까지의 숫자 중에 어떤 숫자를 넣을지 정하는 것이다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[][] arr = new int[n][m];
int[][] ori = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
arr[i][j] = in.nextInt();
ori[i][j] = arr[i][j];
}
}
int max = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 1 || arr[i][j] == 2) continue;
for (int k = i; k < n; k++) {
for (int l = 0; l < m; l++) {
if (k == i && j >= l) continue;
if (arr[k][l] == 1 || arr[k][l] == 2) continue;
int count = 0;
for (int o = k; o < n; o++) {
for (int p = 0; p < m; p++) {
if (o == k && p <= l) continue;
if (arr[o][p] == 1 || arr[o][p] == 2) continue;
arr[i][j] = 1;
arr[k][l] = 1;
arr[o][p] = 1;
for (int a = 0; a < n; a++) {
for (int b = 0; b < m; b++) {
if (arr[a][b] == 2) {
if (a == 0 && b == 0) {
if (arr[a + 1][b] == 0) arr[a + 1][b] = 2;
if (arr[a][b + 1] == 0) arr[a][b + 1] = 2;
} else if (a == 0 && b == m - 1) {
if (arr[a + 1][b] == 0) arr[a + 1][b] = 2;
if (arr[a][b - 1] == 0) arr[a][b - 1] = 2;
} else if (a == n - 1 && b == 0) {
if (arr[a - 1][b] == 0) arr[a - 1][b] = 2;
if (arr[a][b + 1] == 0) arr[a][b + 1] = 2;
} else if (a == n - 1 && b == m - 1) {
if (arr[a - 1][b] == 0) arr[a - 1][b] = 2;
if (arr[a][b - 1] == 0) arr[a][b - 1] = 2;
} else if (a == 0) {
if (arr[a + 1][b] == 0) arr[a + 1][b] = 2;
if (arr[a][b + 1] == 0) arr[a][b + 1] = 2;
if (arr[a][b - 1] == 0) arr[a][b - 1] = 2;
} else if (b == 0) {
if (arr[a + 1][b] == 0) arr[a + 1][b] = 2;
if (arr[a - 1][b] == 0) arr[a - 1][b] = 2;
if (arr[a][b + 1] == 0) arr[a][b + 1] = 2;
} else if (a == n - 1) {
if (arr[a][b - 1] == 0) arr[a][b - 1] = 2;
if (arr[a - 1][b] == 0) arr[a - 1][b] = 2;
if (arr[a][b + 1] == 0) arr[a][b + 1] = 2;
} else if (b == m - 1) {
if (arr[a + 1][b] == 0) arr[a + 1][b] = 2;
if (arr[a][b - 1] == 0) arr[a][b - 1] = 2;
if (arr[a - 1][b] == 0) arr[a - 1][b] = 2;
} else {
if (arr[a + 1][b] == 0) arr[a + 1][b] = 2;
if (arr[a - 1][b] == 0) arr[a - 1][b] = 2;
if (arr[a][b + 1] == 0) arr[a][b + 1] = 2;
if (arr[a][b - 1] == 0) arr[a][b - 1] = 2;
}
}
}
}
for (int a = n - 1; a >= 0; a--) {
for (int b = m - 1; b >= 0; b--) {
if (arr[a][b] == 2) {
if (a == 0 && b == 0) {
if (arr[a + 1][b] == 0) arr[a + 1][b] = 2;
if (arr[a][b + 1] == 0) arr[a][b + 1] = 2;
} else if (a == 0 && b == m - 1) {
if (arr[a + 1][b] == 0) arr[a + 1][b] = 2;
if (arr[a][b - 1] == 0) arr[a][b - 1] = 2;
} else if (a == n - 1 && b == 0) {
if (arr[a - 1][b] == 0) arr[a - 1][b] = 2;
if (arr[a][b + 1] == 0) arr[a][b + 1] = 2;
} else if (a == n - 1 && b == m - 1) {
if (arr[a - 1][b] == 0) arr[a - 1][b] = 2;
if (arr[a][b - 1] == 0) arr[a][b - 1] = 2;
} else if (a == 0) {
if (arr[a + 1][b] == 0) arr[a + 1][b] = 2;
if (arr[a][b + 1] == 0) arr[a][b + 1] = 2;
if (arr[a][b - 1] == 0) arr[a][b - 1] = 2;
} else if (b == 0) {
if (arr[a + 1][b] == 0) arr[a + 1][b] = 2;
if (arr[a - 1][b] == 0) arr[a - 1][b] = 2;
if (arr[a][b + 1] == 0) arr[a][b + 1] = 2;
} else if (a == n - 1) {
if (arr[a][b - 1] == 0) arr[a][b - 1] = 2;
if (arr[a - 1][b] == 0) arr[a - 1][b] = 2;
if (arr[a][b + 1] == 0) arr[a][b + 1] = 2;
} else if (b == m - 1) {
if (arr[a + 1][b] == 0) arr[a + 1][b] = 2;
if (arr[a][b - 1] == 0) arr[a][b - 1] = 2;
if (arr[a - 1][b] == 0) arr[a - 1][b] = 2;
} else {
if (arr[a + 1][b] == 0) arr[a + 1][b] = 2;
if (arr[a - 1][b] == 0) arr[a - 1][b] = 2;
if (arr[a][b + 1] == 0) arr[a][b + 1] = 2;
if (arr[a][b - 1] == 0) arr[a][b - 1] = 2;
}
}
}
}
count = 0;
for (int a = 0; a < n; a++) {
for (int b = 0; b < m; b++) {
if(arr[a][b] == 0) count++;
}
}
if(count > max) {
max = count;
}
for (int a = 0; a < n; a++) {
for (int b = 0; b < m; b++) {
arr[a][b] = ori[a][b];
}
}
}
}
}
}
}
}
System.out.println(max);
}
}
살다살다 8중 for문을 쓸 줄이야 내가 조합(Combination)을 코드로 구현할 줄 몰라서 무식한 방법으로 했다
예제 입력을 입력으로 넣었을 때는 모두 옳은 답이 나오는데 제출하면 틀리다고 한다.
예제 입력1예제 입력2예제 입력3
아직도 못 풀었지만 꼭 내 손으로 풀 거다
2020.01.14
이후에 순열과 조합 알고리즘을 공부하고 오늘 다시 도전해보았다
def permutation(result, num, n, li):
if num == 3:
v = [[False] * m for i in range(n)]
import collections
q = collections.deque()
for i in virus:
q.append((i[0], i[1]))
while q:
cur = q.popleft()
v[cur[0]][cur[1]] = True
if cur[0] - 1 >= 0 and li[cur[0] - 1][cur[1]] == 0 and not v[cur[0] - 1][cur[1]]:
q.append((cur[0] - 1, cur[1]))
if cur[0] + 1 < n and li[cur[0] + 1][cur[1]] == 0 and not v[cur[0] + 1][cur[1]]:
q.append((cur[0] + 1, cur[1]))
if cur[1] - 1 >= 0 and li[cur[0]][cur[1] - 1] == 0 and not v[cur[0]][cur[1] - 1] :
q.append((cur[0], cur[1] - 1))
if cur[1] + 1 < m and li[cur[0]][cur[1] + 1] == 0 and not v[cur[0]][cur[1] + 1]:
q.append((cur[0], cur[1] + 1))
count = 0
for i in range(n):
for j in range(m):
if li[i][j] == 0 and not v[i][j]:
count += 1
c.append(count)
return
for i in range(n):
for j in range(m):
if not visited[i][j]:
if li[i][j] == 0:
if num > 0:
if result[num - 1][0] < i:
result[num] = (i, j)
visited[i][j] = True
li[i][j] = 1
permutation(result, num + 1, n, li)
visited[i][j] = False
li[i][j] = 0
elif result[num - 1][0] == i and result[num - 1][1] < j:
result[num] = (i, j)
visited[i][j] = True
li[i][j] = 1
permutation(result, num + 1, n, li)
visited[i][j] = False
li[i][j] = 0
else:
continue
else:
result[num] = (i, j)
visited[i][j] = True
li[i][j] = 1
permutation(result, num + 1, n, li)
visited[i][j] = False
li[i][j] = 0
from sys import stdin
n, m = list(map(int, stdin.readline().split()))
li = []
virus = []
for i in range(n):
temp = list(map(int, stdin.readline().split()))
li.append(temp)
for j in range(m):
if temp[j] == 2:
virus.append((i, j))
visited = [[False] * m for i in range(n)]
r = [(0, 0)] * 3
c = []
permutation(r, 0, n, li)
print(max(c))
시간초과가 뜬다... 조합이 재귀함수라서 그런걸까
6시간 뒤
성공! 위와 코드는 똑같은데 큐에 들어가 있는 것을 중복으로 집어넣는 것을 방지해주었더니 바로 해결됐다.
오늘 또 교훈을 얻는다. 큐에 넣을 때 visited를 True로 바꾸자
def permutation(result, num, n, li):
if num == 3:
v = [[False] * m for i in range(n)]
import collections
q = collections.deque()
for i in virus:
q.append((i[0], i[1]))
while q:
cur = q.popleft()
if not v[cur[0]][cur[1]] and li[cur[0]][cur[1]] == 0:
v[cur[0]][cur[1]] = True
if cur[0] - 1 >= 0 and li[cur[0] - 1][cur[1]] == 0 and not v[cur[0] - 1][cur[1]]:
q.append((cur[0] - 1, cur[1]))
v[cur[0] - 1][cur[1]] = True
if cur[0] + 1 < n and li[cur[0] + 1][cur[1]] == 0 and not v[cur[0] + 1][cur[1]]:
q.append((cur[0] + 1, cur[1]))
v[cur[0] + 1][cur[1]] = True
if cur[1] - 1 >= 0 and li[cur[0]][cur[1] - 1] == 0 and not v[cur[0]][cur[1] - 1] :
q.append((cur[0], cur[1] - 1))
v[cur[0]][cur[1] - 1] = True
if cur[1] + 1 < m and li[cur[0]][cur[1] + 1] == 0 and not v[cur[0]][cur[1] + 1]:
q.append((cur[0], cur[1] + 1))
v[cur[0]][cur[1] + 1] = True
count = 0
for i in range(n):
for j in range(m):
if li[i][j] == 0 and not v[i][j]:
count += 1
c.append(count)
return
for i in range(n):
for j in range(m):
if not visited[i][j]:
if li[i][j] == 0:
if num > 0:
if result[num - 1][0] < i:
result[num] = (i, j)
visited[i][j] = True
li[i][j] = 1
permutation(result, num + 1, n, li)
visited[i][j] = False
li[i][j] = 0
elif result[num - 1][0] == i and result[num - 1][1] < j:
result[num] = (i, j)
visited[i][j] = True
li[i][j] = 1
permutation(result, num + 1, n, li)
visited[i][j] = False
li[i][j] = 0
else:
continue
else:
result[num] = (i, j)
visited[i][j] = True
li[i][j] = 1
permutation(result, num + 1, n, li)
visited[i][j] = False
li[i][j] = 0
from sys import stdin
n, m = list(map(int, stdin.readline().split()))
li = []
virus = []
for i in range(n):
temp = list(map(int, stdin.readline().split()))
li.append(temp)
for j in range(m):
if temp[j] == 2:
virus.append((i, j))
visited = [[False] * m for i in range(n)]
r = [(0, 0)] * 3
c = []
permutation(r, 0, n, li)
print(max(c))
