oneway's history

File -> Project Structure -> Project Settings 의 Modules 에서

src 폴더를 한 번 클릭해준 뒤

바로 위에 Mark as 에 Sources 를 클릭해서 파랑색으로 바꿔주면 됨.

참고: https://stackoverflow.com/questions/54898947/unable-to-create-java-package-in-maven-project-imported-in-intellij

https://www.acmicpc.net/problem/24444

[실패] 라고 떠있길래 이걸 왜못풀었지? 싶었는데 못푼 이유가 있었다.

시간복잡도를 상당히 신경써야 하는 문제...

그냥 대충 행렬로 만들면 안됐다.

이전에 자바로 [실패] 를 엄청 많이 했길래 이걸 못풀었어? 하고 슥 풀라했다가

이번에도 [실패] 난무했다.

항상 풀던대로 visited 를 이용해줬는데,

얘를 빼고 풀어보니 통과가 됐다.

그리고 answer 리스트에 답을 담는 과정에서 불필요하게 if문이 도는걸 막았다.

import sys
from collections import deque
input = sys.stdin.readline
N, M, R = map(int, input().split())
graph = [[] for i in range(N+1)]
# visited = [False for i in range(N+1)]
answer = [0 for i in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(1, N+1):
    graph[i].sort()


queue = deque()
queue.append(R)
answer[R] = 1
cnt = 2
while queue:
    num = queue.popleft()
    # visited[num] = True
    # if answer[num] == 0:
    #     answer[num] = cnt
    #     cnt += 1

    for idx in graph[num]:
        if answer[idx] == 0:  # 방문한적 없으면 고
            queue.append(idx)
            answer[idx] = cnt
            cnt += 1

for i in answer[1:]:
    print(i)

# visited 이녀석 생성하는 시간이 오래걸렸나? 
# visited 역할을 answer가 대신 하게 해줬더니 통과됐다.

https://www.acmicpc.net/problem/24479

1. 자바로 풀때처럼 리스트 형식으로 구현할라고 했는데, 정점 수가 많아서 메모리 초과가 났다.

  -> 그래서 연결된 부분만 입력받도록 append 하는거로 바꿈

  -> 오름차순 컨셉 유지하기위해 graph의 모든 부분을 오름차순함.

2. 재귀로 DFS 할라했는데, 간선이 20만개로 너무 많아서 계속 Recursion Error 남. IDE에선 잘 돌아가는데.

  -> 그래서 그냥 Stack 과 While 문으로 해결함.

  -> Stack을 쓰다보니 앞쪽부터 빼가니까 graph를 내림차순으로 바꿈

import sys
from collections import deque
input = sys.stdin.readline
N, M, R = map(int, input().split())
# graph = [[False for i in range(N+1)] for i in range(N+1)]
graph = [[] for i in range(N+1)]
visited = [False for i in range(N+1)]
answer = [0 for i in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    # graph[a][b] = graph[b][a] = True
    graph[a].append(b)
    graph[b].append(a)

for i in range(N+1):
    # graph[i].sort()
    graph[i].sort(reverse=True)

# print(graph)
cnt = 1


# def dfs(num):
#     visited[num] = True
#     global cnt
#     # answer[cnt] = num
#     if answer[num] == 0:
#         answer[num] = cnt
#         cnt += 1
#     for idx in range(len(graph[num])):
#         s = graph[num][idx]
#         # 간선으로 연결되어있고 이미 방문하지 않았다면
#         # if graph[num][idx] == True and visited[idx] == False:
#         if visited[s] == False:
#             dfs(s)


# dfs(R)

stack = deque()
stack.append(R)

while stack:
    num = stack.pop()
    visited[num] = True
    if answer[num] == 0:
        answer[num] = cnt
        cnt += 1

    for idx in graph[num]:
        if visited[idx] == False:
            stack.append(idx)


for i in range(1, N+1):
    print(answer[i])

# 1. 전체를 리스트로 담다보니 메모리 초과남
# 2. 재귀를 쓰려다보니 간선이 200000개가 최대라 recursion error 뜸
# 3. 스택쓰고 while 쓴다.

그래프 문제를 너무 오랜만에 풀어서 그런가 꽤나 오래걸렸다.

https://www.acmicpc.net/problem/2589

요령

1. 냅다 2차원 배열의 처음부터 끝까지 탐색하면서 "L" 인 녀석을 찾는다.

2. 그녀석부터 시작해서 BFS를 탐색하는데, 다음 칸으로 넘어갈 때마다 time 을 1씩 더해주면서 간다.

3. 매번 time이 갱신될 때마다 전역변수에 있는 result와 비교해서 최대값으로 갱신해준다.

풀면서 배운점

1. 입력받을 때, 문자 사이에 빈 칸이 없을 때 2중 for문으로 직접 append 해주었는데, 한 줄로 쓸 수 있는 방법을 배웠다.

심지어 별로 속도 차이도 안남.

(2중 for문 했을 때 820ms, 한 줄로 입력받았을 때 816ms 였다)

mmap = [[] for i in range(R)]
for i in range(R):
	s = input().rstrip()
	for j in s:
    	mmap[i].append(j)

mmap = [list(input()) for i in range(R)]

풀이 코드

import sys
from collections import deque
input = sys.stdin.readline
R, C = map(int, input().split())
mmap = [[] for i in range(R)]
visited = [[False for i in range(C)] for i in range(R)]
result = 0
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
for i in range(R):
    s = input().rstrip()
    for j in s:
        mmap[i].append(j)


def bfs():
    # print("\nbfs 시작")
    while queue:
        r, c, time = queue.popleft()
        # print(r, c, time)
        global result
        result = max(time, result)
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 > nr or nr >= R or 0 > nc or nc >= C or mmap[nr][nc] == "W" or tvisited[nr][nc] == True:
                continue
            queue.append((nr, nc, time+1))
            tvisited[nr][nc] = True


for r in range(R):
    for c in range(C):
        if mmap[r][c] == "L":
            queue = deque()
            queue.append((r, c, 0))
            tvisited = [m[:] for m in visited]
            tvisited[r][c] = True
            bfs()

print(result)

항상 자바로 풀다가 파이썬으로 그래프 문제를 풀어봤다.

이 문제에서 배운 점:

1. import copy 해서 2차원 배열을 deepcopy 하는 방법은 slicing 해서 복사 하는 것보다 훨씬 느리다는 점.

(deepcopy를 사용하면 3136ms, 사용하지 않으면 1676ms 가 나왔다.)

2. 자바로 풀던때가 적응돼서 visited 배열을 꼭 따로 만들어줬었는데, 그럴필요 없다는 점

3. append 할 때 [nr, nc] 처럼 리스트가 아니라 (nr, nc) 해서 튜플로 해주면 더 빠르다는점.

(리스트 썼을 때 1860ms, 튜플로 썼을 때 1676ms 가 나왔다.)

4. import time 이란걸 사용해서 꼭 백준에 제출하지 않더라도 코드 실행시간을 체크할 수 있다는 점을 알았다.

import sys
# import copy
# import time
from collections import deque
# start = time.time()
input = sys.stdin.readline
R, C = map(int, input().split())
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
mmap = []
answer = 0
for i in range(R):
    mmap.append(list(map(int, input().split())))


def bfs():
    queue = deque()
    tmap = [m[:] for m in mmap]
    # tmap = copy.deepcopy(mmap)
    for i in range(R):
        for j in range(C):
            if tmap[i][j] == 2:
                queue.append((i, j))

    while queue:
        r, c = queue.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 > nr or nr >= R or 0 > nc or nc >= C:
                continue
            if tmap[nr][nc] == 0:
                tmap[nr][nc] = 2
                queue.append((nr, nc))

    global answer
    cnt = 0
    for i in range(R):
        cnt += tmap[i].count(0)
    answer = max(answer, cnt)


def backtrack(cnt):
    if cnt == 3:
        bfs()
        return
    for i in range(R):
        for j in range(C):
            if mmap[i][j] == 0:
                mmap[i][j] = 1
                backtrack(cnt+1)
                mmap[i][j] = 0


backtrack(0)
print(answer)
# print("time : ", time.time() - start)

대충 이런 형태로 만들고 싶을 때, 만드는 방법을 설명해보겠습니다.

맨날 노션페이지 새로 만들때마다 까먹어서 기록해버림.

화면이 커서 좀 작은데, 왼쪽 그림에서 빨강색 화살표가 가리키는 점 6개를 눌러주세요.

누르시면 오른쪽 이미지처럼 "페이지로 전환" 이라는 버튼이 있습니다.

클릭~

그러면 위 사진처럼 회의록 캘린더가 하나의 페이지속으로 들어갑니다.

이 때 옆으로 갖다놓을 블럭을 하나 만들어둡니다.

새로 만든 블럭의 점 6개를 끌어다가 작아진 캘린더의 오른쪽으로 갖다대면 파랑색 바가 | 형태로 누울겁니다.

그때 마우스를 놓으면 가로로 나열됩니다.

이렇게 나열됐다면 위 사진처럼 점 6개를 누르고 "인라인으로 전환" 버튼을 눌러서 

캘린더를 인라인 형태로 변환해주면 됩니다.

뾰롱~

경계에 마우스를 갖다대면 선이 생기는데, 그걸 잡고 크기조절을 할 수 있습니다.

블럭을 오른쪽으로 더 추가하여 더 가로로 배열할 수 있습니다.

https://www.acmicpc.net/problem/2583

직사각형으로 덮힌 부분을 1, 안덮힌 부분을 0 로 저장,

모든 경우를 탐색하며 0일 때 BFS 시작하여 while 이 끝날 때 pieces가 1 추가되게 해서 분리된 영역의 개수를 구했고

BFS 돌때마다 getArea를 1씩 더해주며 그 넓이를 구했습니다.

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_백준_2583_영역구하기_실버1_144ms {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk = new StringTokenizer(br.readLine());
		int R = Integer.parseInt(stk.nextToken());
		int C = Integer.parseInt(stk.nextToken());
		int K = Integer.parseInt(stk.nextToken());
		int[][] map = new int[R][C];
		for (int i = 0; i < K; i++) {
			stk = new StringTokenizer(br.readLine());
			int x1 = Integer.parseInt(stk.nextToken());
			int y1 = Integer.parseInt(stk.nextToken()); // 왼쪽위
			int x2 = Integer.parseInt(stk.nextToken());
			int y2 = Integer.parseInt(stk.nextToken()); // 오른아래

			for (int j = y1; j < y2; j++) {
				for (int k = x1; k < x2; k++) {
					map[j][k] = 1;
				}
			}
		}

		int[] dr = { -1, 1, 0, 0 };
		int[] dc = { 0, 0, -1, 1 };
		boolean[][] visited = new boolean[R][C];
		ArrayList<Integer> arr = new ArrayList<Integer>();
		Queue<int[]> q = new LinkedList<int[]>();
		int pieces = 0, getArea = 0;
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (map[i][j] == 0 && !visited[i][j]) {
					pieces++;
					getArea = 1;
					q.offer(new int[] { i, j });
					visited[i][j] = true;
					while (q.size() > 0) {
						int r = q.peek()[0];
						int c = q.poll()[1];
						for (int k = 0; k < 4; k++) {
							int nr = r + dr[k];
							int nc = c + dc[k];
							if (0 > nr || nr >= R || 0 > nc || nc >= C || visited[nr][nc] || map[nr][nc] == 1) {
								continue;
							}
							getArea++;
							q.offer(new int[] { nr, nc });
							visited[nr][nc] = true;
						}
					}
					arr.add(getArea);
				}
			}
		}
		System.out.println(pieces);
		Collections.sort(arr);
		for (int i = 0; i < arr.size(); i++) {
			System.out.print(arr.get(i) + " ");
		}
	} // 메인 끝
}

결과

https://www.acmicpc.net/problem/4963

섬인지 아닌지 체크하는 부분을 BFS를 이용해 visited 체크해가며 반복문을 도는 방식으로 풀어주었습니다.

시간 효율을 조금이나마? 늘리기 위해 일반 map의 행과 열의 크기를 2씩 넓게 해서 if문 사용을 줄였습니다.

package baekjoon;

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_백준_4963_섬의개수_실버2_188ms {
	private static int[] dr = {-1,-1,0,1,1,1,0,-1}; // 12시부터 시계방향
	private static int[] dc = {0,1,1,1,0,-1,-1,-1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk;
		StringBuilder sb = new StringBuilder();
		while(true) {
			stk = new StringTokenizer(br.readLine());
			int w = Integer.parseInt(stk.nextToken());
			int h = Integer.parseInt(stk.nextToken());
			if (w == 0 && h == 0) break;
			int[][] map = new int[h+2][w+2];
			boolean[][] visited = new boolean[h+2][w+2];
			for (int i = 1; i <= h; i++) {
				stk = new StringTokenizer(br.readLine());
				for (int j = 1; j <= w; j++) {
					map[i][j] = Integer.parseInt(stk.nextToken());
				}
			}
			
			int cnt = 0;
			Queue<int[]> q = new LinkedList<int[]>(); 
			for (int r = 1; r <= h; r++) {
				for (int c = 1; c <= w; c++) {
					if (map[r][c] == 1 && !visited[r][c]) {
						cnt++;
						q.offer(new int[] {r, c});
						while(q.size() > 0) {
							int rr = q.peek()[0];
							int cc = q.poll()[1];
							for (int i = 0; i < 8; i++) {
								int nr = rr + dr[i];
								int nc = cc + dc[i];
								if (map[nr][nc] == 1 && !visited[nr][nc]) {
									q.offer(new int[] {nr, nc});
									visited[nr][nc] = true;
								}
							}
						} // while 끝
					}
				}
			}
			sb.append(cnt).append("\n");
		} // while 끝
		System.out.println(sb);
	} // 메인 끝
}

결과