그런데 최소 한개의 옷을 입여야 하기 때문에 [none, none, none, none]을 고른 경우의 수 1개를 빼주어야 한다.
따라서 23가지
[코드]
public static int solution(String[][] clothes) {
Map<String, Integer> hm = new HashMap<>();
for (int i=0; i<clothes.length; i++) {
hm.put(clothes[i][1], hm.getOrDefault(clothes[i][1], 1) + 1);
}
int ans = 1;
for (Integer value : hm.values()) {
ans *= value;
}
return ans-1;
}
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.
어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.
[문제 풀이]
이 문제는 BFS 또는 DFS를 이용하여 해결 할 수 있다.
그리고 BFS와 DFS를 구현하는데 matrix 또는 list로 구현이 가능한데 두 가지 방법으로 다 풀어보았다.
1. BFS Linked list
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static Queue<Integer> q = new LinkedList<>();
static boolean[] visited;
static Node[] adj;
static int stoi(String s) {
return Integer.parseInt(s);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = stoi(br.readLine());
M = stoi(br.readLine());
visited = new boolean[N+1];
adj = new Node[N+1];
for (int i=0; i<M; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int u = stoi(st.nextToken());
int v = stoi(st.nextToken());
adj[u] = new Node(v, adj[u]);
adj[v] = new Node(u, adj[v]);
}
System.out.println(bfs(1));
}
public static int bfs(int n) {
int cnt = 0;
visited[n] = true;
q.offer(n);
while(!q.isEmpty()) {
int x = q.poll();
for (Node node=adj[x]; node!=null; node=node.next) {
if (!visited[node.n]) {
q.offer(node.n);
visited[node.n] = true;
cnt++;
}
}
}
return cnt;
}
static class Node {
int n;
Node next;
public Node(int n, Node next) {
this.n = n;
this.next = next;
}
}
}
2. DFS Linked list
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int n, m;
static Node[] adj;
static boolean[] visit;
static int cnt;
public static int stoi(String s) {
return Integer.parseInt(s);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = stoi(br.readLine());
m = stoi(br.readLine());
adj = new Node[n+1];
visit = new boolean[n+1];
for (int i=0; i<m; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int u = stoi(st.nextToken());
int v = stoi(st.nextToken());
adj[u] = new Node(v, adj[u]);
adj[v] = new Node(u, adj[v]);
}
dfs(1);
System.out.println(cnt);
}
public static void dfs(int v) {
visit[v] = true;
for (Node node=adj[v]; node!=null; node=node.next) {
if (!visit[node.n]) {
cnt++;
dfs(node.n);
}
}
}
static class Node {
int n;
Node next;
public Node(int n, Node next) {
this.n = n;
this.next = next;
}
}
}
3. DFS Matrix
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int n, m;
static int[][] matrix;
static boolean[] visit;
static int cnt;
public static int stoi(String s) {
return Integer.parseInt(s);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = stoi(br.readLine());
m = stoi(br.readLine());
matrix = new int[n+1][n+1];
visit = new boolean[n+1];
for (int i=0; i<m; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int u = stoi(st.nextToken());
int v = stoi(st.nextToken());
matrix[u][v] = 1;
matrix[v][u] = 1;
}
dfs(1);
System.out.println(cnt);
}
public static void dfs(int v) {
visit[v] = true;
for (int i=1; i<=n; i++) {
if (matrix[v][i]==1 && !visit[i]) {
cnt++;
dfs(i);
}
}
}
}
전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.
이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.
[문제 풀이]
전위 순회 (루트, 왼쪽, 오른쪽) 로 입력이 들어올때 노드를 생성하며 tree 구조로 만들어 주었다.
만들어진 tree 구조에서 후위 순회를 하며 결과를 하나씩 출력해 주었다.
[코드]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static Node root;
static StringBuilder sb = new StringBuilder();
static int stoi(String s) {
return Integer.parseInt(s);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
root = new Node(stoi(br.readLine()));
// 노드 생성 트리 생성
String n;
while(true) {
n = br.readLine();
if (n == null || n.equals("")) break;
Node node = new Node(stoi(n));
connectNode(root, node);
}
// 후위 순회
postOrder(root);
System.out.println(sb);
}
static void postOrder(Node node) {
if (node.left != null) postOrder(node.left);
if (node.right != null) postOrder(node.right);
sb.append(node.num).append("\n");
}
static void connectNode(Node cur, Node next) {
if (next.num < cur.num) {
if (cur.left != null) {
connectNode(cur.left, next);
} else {
cur.left = next;
}
} else {
if (cur.right != null) {
connectNode(cur.right, next);
} else {
cur.right = next;
}
}
}
static class Node {
int num;
Node left;
Node right;
Node(int num) {
this.num = num;
}
}
}
