oneway's history

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

BFS로 최단거리 찾기 문제인데, 3차원인 경우이다.

따라서 배열을 3중으로 사용하였다.

그것만 헷갈리지 않으면 전혀 어렵지 않은 문제.

정답 풀이:

import sys
from collections import deque
input = sys.stdin.readline

dh = [-1, 1, 0, 0, 0, 0]
dr = [0, 0, -1, 1, 0, 0]
dc = [0, 0, 0, 0, -1, 1]

while True:
    h, r, c = map(int, input().split(" "))
    if h == 0 and r == 0 and c == 0:
        break

    sh, sr, sc = -1, -1, -1
    eh, er, ec = -1, -1, -1

    graph = []
    for H in range(h):
        tgraph = []
        for R in range(r):
            tlist = list(map(str, input().rstrip()))

            for C in range(c):
                if tlist[C] == 'S':
                    sh, sr, sc = H, R, C
                elif tlist[C] == 'E':
                    eh, er, ec = H, R, C

            tgraph.append(tlist)
        graph.append(tgraph)
        input()

    queue = deque()
    visited = [[[False for _ in range(c)] for _ in range(r)] for _ in range(h)]
    queue.append((sh, sr, sc, 0))
    visited[sh][sr][sc] = True

    escapeTime = -1
    while queue:
        H, R, C, time = queue.popleft()

        if H == eh and R == er and C == ec:
            escapeTime = time
            break

        for i in range(6):
            nh = H + dh[i]
            nr = R + dr[i]
            nc = C + dc[i]

            if 0 <= nh < h and 0 <= nr < r and 0 <= nc < c and graph[nh][nr][nc] != '#' and visited[nh][nr][nc] == False:
                queue.append((nh, nr, nc, time+1))
                visited[nh][nr][nc] = True

    if escapeTime == -1:
        print("Trapped!")
    else:
        print("Escaped in {} minute(s).".format(escapeTime))

결과

오타 하나 나서 틀렸었다 ^^..

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/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)

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);
	} // 메인 끝
}

결과