그런데 최소 한개의 옷을 입여야 하기 때문에 [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);
}
}
}
}
